Yes, you can use astral projection from planes other than the Material Plane. The Manual of the Planes describes how spells that access transitive planes such as the Astral Plane function on other planes in the section "Moving Among Transitive Planes" (starting on page 45).
Characters generally must use spells or spell-like abilities to access a Transitive
Plane. ... the astral projection spell takes you to the Astral Plane ... Such spells should function in any location coexistent with or coterminous to the plane.
It includes various examples of travel between transitive planes on page 46. These examples reinforce that "Material Plane" is a placeholder and that you can use astral projection from anywhere that is connected to the astral plane. Your body will be left behind on the plane you project from.
From the Ethereal Plane to the Astral Plane: You can move to the Astral Plane from almost everywhere on the Ethereal Plane, because the Astral Plane connects to everywhere on the Ethereal Plane. ... If you're using an astral projection spell, your physical body remains in the Ethereal Plane ...
From the Plane of Shadow to the Astral Plane: From the Plane of Shadow, you can use the astral projection spell, leaving your body behind on that plane ...
The spell "Locate City" has a range of 10 miles per caster level, and allows the sense of distance and direction to the "nearest community of a minimum size designated by you at time of casting." With nearest being counted without movement through solid objects.
Thus, with a sufficiently large caster level, a sufficiently accurate census, and a sufficiently large population density of villages and cities, it should be quite possible to get a very good idea of where a person is based on gated counts of censuses.
The trick to building a navigation network out of this is by creating artificial communities in "known positions" which count for purposes of this spell. (How to do that is functionally a DM call, but a metropolis built in great miniature with undead squirrels haunt-shifted into it to count as "occupants" suspended in the sky isn't a... horrible option.) For each of these metropoli, anchor to them to the sky via 3 immovable rods within a spacing dedicated by the modal range of the spell being used (which itself becomes a question of assets and magic item economies.)
Much like with dGPS, since you can set the community size of each of these, it turns into a 4-colour map problem equivalent. By knowing north, having a chart of these undead beacons, and casting the spell N times (where N is the set of granularities allowed for by "minimum population" in the spell), you can get a direction and distance to each of the nearest "population-unique" beacons. Then it's a matter of triangulating against the map to identify where the individual is.
Circle dance would be preferable (as it has no maximum range), save for the fact that it requires firsthand knowledge of a creature, which rather reduces the utility, (though being taken on a tour of the "sky thrones" and meeting the undead squirrels sitting on each would itself, be hilarious). If you're OK with houserules, you can probably assert that each squirrel's truename can count as firsthand knowledge of them for purposes of circle dance. Then it's merely a matter of referencing the appropriate truenames of the beacons, and finding where the vectors intersect. But that's much less cool.
...
Or they can just cast find the path (or Knowledge(Geography) perhaps boosted to absurd levels with divine insight or improvisation) to get there and if visibility prevents landing due to some obscure house-rule, use dispel fog to clear a lane to your landing area and blindsight and/or true seeing and/or short range teleportation and/or feather fall to deal with any traps or concerns at the landing pad.
Best Answer
A really key point to consider here is that 5e’s teleport is a 7th-level spell, and without an associated object, attempting to teleport to a location without a permanent teleport circle is only 75% accurate even if you are very familiar.1
By contrast, teleport is a 5th-level spell in 3.5e, the same as 5e’s teleport circle, and if you are very familiar,1 it is 97% accurate. So unlike 5e, where a permanent circle is necessary to teleport long distances with a 5th-level spell at all, in 3.5e all it would really do is improve your accuracy by 3 percentage points.
So no, D&D 3.5e doesn’t have anything that’s all that similar to 5e’s teleportation circle, because 3.5e’s teleportation magic is far more powerful and doesn’t need one. Adding something like it—unless you made it a lower spell level than 5th—won’t change very much and doesn’t seem like something that would be worth very much effort for destinations to set up. If you make it lower-level, and thus make long-distance teleportation—to particular destinations, but still—available at a lower level, that’s going to change a lot about your world. It also is maybe weird with how spell levels progress—if you make it 4th level, it’s the same level as dimension door, which is very much short-distance teleportation, and highly limited teleportation at that. Might be kind of weird.
On the flip side, if you removed 3.5e’s teleport, teleport object, greater teleport, teleportation circle, and any other long-distance teleportation found in supplements, and then added 5e’s teleportation circle and teleport as replacements, then these permanent circles would have a purpose—much the same as they have in 5e. (You probably want to move plane shift up to 7th spell level for clerics, too, in this process.) The effect of this would be to limit the availability of long-distance teleportation—which in my mind, is probably a good thing. Teleport is an incredibly game-warping spell, pushing it off another four character levels helps. Makes it so scry ‘n’ die is only an option that much later, which is good. The really big problem, though, is the mountain of 3.5e material out there—you would have to you would have to find and rework every existing long-range teleportation spell from supplements, to make them work appropriately in the new system, and then you’d have to worry about every monster that could be summoned, called, or turned into, as those may provide ways to circumvent the rule, and so on. Handling that on an ad hoc basis is probably fine—probably the only realistic way to do it—but you have to have a group that is mature and on-board enough to respect the houserule and not look for ways to circumvent it.
Just as an aside, the closest thing actually in 3.5e that I can find for this is Faerûn’s portals.
Forgotten Realms Campaign Setting has the Create Portal feat, with associated rules for portals in Chapter 2. A portal, however, is almost like the opposite of 5e’s teleportation circle—a permanent place you can teleport from, rather than to. More importantly, though, they can be used by anyone—no need to know and cast a 5th-level spell to use them. Anyway, a portal is valued at 100,000 gp, so creating one costs 50,000 gp and 4,000 XP, and takes 100 days, so there is some similarity in the process. (In D&D 3.5e, hiring someone to cast a 5th-level spell costs 450 gp, so doing that every day would cost 164,250 gp, so substantially more than the portal but in the right neighborhood.)
Similar to these portals is making the 3.5e teleportation circle permanent with the spell permanency, which produces something quite like these portals. Thanks to Lino Frank Ciaralli’s answer for pointing that out.