Here is what I hope is an intuitive argument that it does not need to be the case that the exhaust velocity is greater than whatever velocity the rocket is to achieve.
First of all, think about a 'rocket' which is powered by someone sitting in the back throwing pebbles out of it. The pebbles weigh $0.1\,\mathrm{kg}$ and the person can throw them at $10\,\mathrm{m/s}$ relative to the rocket.
At some point the person has thrown all but one pebble. The remaining mass of the rocket and the person is $100\,\mathrm{kg}$, so the total mass of the thing, including the pebble, is $100.1\,\mathrm{kg}$.
So what happens when the person throws this last pebble? Well, we can use conservation of momentum to tell us: If the rocket is travelling at $v$ just before the pebble is thrown, then its initial momentum is $100.1v$. Afterwards, the pebble is going at $v - 10$, so the final momentum is $100 (v + \Delta v) + 0.1(v - 10)$, where $\Delta v$ is the change in speed. So we know these are the same, so
$$100.1v = 100(v + \Delta v) + 0.1(v - 10)$$
And from this we work out that $\Delta v = 1/100\,\mathrm{m/s}$: it does not depend on $v$ at all.
Well, OK. So let's imagine now that, just before the last pebble is thrown, the rocket was travelling at $11\,\mathrm{km/s} - 0.005\,\mathrm{m/s}$. Well, just after the pebble is thrown is it now travelling at $11\,\mathrm{km/s} + 0.005\,\mathrm{m/s}$: it's now going faster than $11\,\mathrm{km/s}$.
But the pebble was thrown at far, far less than $11\,\mathrm{km/s}$
And obviously this is true for any velocity: if I start at $0\,\mathrm{km/s}$ and I have enough pebbles to throw, I can get to any velocity I like.
I will need a lot of pebbles though.