GPS satellites are NOT in Geostationary orbit

I met one more person over the weekend who was sure that the Global Positioning System's 24 satellites were in Geostationary orbit. I have been especially surprised when this opinion is exhibited engineering students who have stated their favourite subject was satellite communications.

I have only an inkling as to why people might be labouring under this misconception. For a GPS device to figure out its own position, it needs to know its distance from at least 4 points whose location is known. The easiest way to find 4 satellites whose location can always be known would be to put them in Geostationary Orbits also known as Geosynchronous Equatorial Orbits (GEO). However, GEO is only possible if the satellite is placed in orbit exactly above the equator.
Geostationary orbits mean that the satellite is hovering above the same spot on the surface of the earth and moves around the planet once in 24 hours (23 hours 56 minutes 4.0916 seconds if you want to be precise). To an observer on the earth, the satellite will appear stationary.

Here is the problem with putting the 24 satellites in GEO. If we place 24 of them in GEO orbit, equally spaced, then only 6 will be visible from any point on the equator, the rest will be over the horizon. Moreover, and more problematic, they would all be in the same plane.

The GPS satellites are therefore in circular orbits with an orbital period of half a sidereal day, meaning they pass over the same spot on the face of the earth twice a day. If your handheld device can now get a distance from 4 satellites, it can figure out its own location in three dimensions.

But here's a puzzle for you. It would be easy to locate a satellite in a GEO. How does the GPS device know the location of the satellite it receives a signal from? To be fair, that is a trick question. The correct question to ask is this: how does the satellite know where it is before it can tell the GPS receiver its location?