I think there's a few people (t'Hooft if I remember correctly?) that believe a quantum computer will never be able to experimentally demonstrate this speed-up because some aspect of quantum mechanics is incomplete/incorrect.
Edit: Here's the thread I was thinking of where t'Hooft and Shor discuss this http://physics.stackexchange.com/questions/34217/why-do-peop...
http://rjlipton.wordpress.com/2013/04/27/sex-lies-and-quantu...
Yes, 't Hooft and others, including Leonid Levin and Oded Goldreich, believe that quantum computers won't function because of quantum mechanics breaking down. See, e.g.:
I.e. isn't quantum superposition just a form of parallelization? if the quantum step in Shor's algorithm is replaced with a classical step executed in parallel in many cpus, then the speed up would be of the same order of magnitude as when using a quantum step.
http://en.wikipedia.org/wiki/Shor's_algorithm#Finding_the_pe...
Shor's algorithm is still very theoretical though, we need to actually build a quantum computer to run it first.
The quantum search algorithm is very interesting. However, most people in the field would, I think, agree that a non-oracle separation between quantum and classical would be vastly more interesting. Oracle results feel a little too close to cheating.
There is, incidentally, a nice paper showing that for computing total Boolean functions the quantum oracle model can be no more than polynomially faster than a classical model. This means there can be no exponential speedup for such functions, which is a real pity.