While it is true that the solutions to the Schrodinger Equation given a constant potential are plane waves, one has to keep in mind that a particle need not be in an energy eigenstate. In fact, since infinite quantities (the uncertainty in position in this case) are widely assumed to be unphysical, the particle *must* be localized to some extent. The particle could very well be almost completely-localized, since the Fourier transform of a delta function is unity (see waves).

Perhaps a more realistic paradox is this: if only a single atom exists, and its energy is measured, collapsing its wavefunction into an energy eigenstate, we get a completely delocalized particle. This implies that infinite quantities--the uncertainty in position here--are physical.