But you always know at least some information about the location. For example you know it's in the visible universe, which puts an upper bound to its location, and therefor it's momentum.

But don't forget the Time<-->Energy uncertainty. If you know the energy of a particle very exactly you don't know how time will pass for it.