Correlation is
$$ \rho_{X,Y} = {\sigma_{X,Y} \over \sigma_X \sigma_Y} $$
Your problem is that you dou don't know $\sigma_Y$, have only loose idea of desired $\rho_{X,Y}$ (> 0.5), don't know $\sigma_{X,Y}$ and allow $\sigma_X$ to be possibly any value, then there is infinitely many solutions for such problem. At the same time
I input a vector $X$ into a black box. This box knows $Y$ and
spits out the correlation of $X$ and $Y$. What vector $X$ do I have to feed
the box to get a high correlation.
what makes your problem hopeless since among infinite possible values only some are correct. Notice also that your question is contradictory, because you say
I don't know what is in $Y$ and I cannot use it to generate $X$.
and at the same time, you want to generate $X$ such that it is dependent on $Y$ (correlation measures dependence, or degree of association). Independently of $Y$ you want to generate $X$ that is dependent on it.
In this case possibly the only thing that you could do is to generate some totally random data and hope that by pure luck one of the samples will appear correlated with $Y$. To be more efficient, you could try to learn from output of your black box and somehow adapt (e.g. using some genetic algorithm) based on output (correlations returned by the black box).