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.