Tree cover and valleys as well as phone placement or orientation can have a massive effect on gps signal

Very true, but on a search like this, narrowing a location down to even a couple miles GREATLY reduces the search area.

They use 'assisted GPS', which requires cell service for a reliable reading

Assisted GPS just helps with a faster initial acquisition. You can put your phone in airplane mode to test it out. It might be a little slower to acquire, but you'll get good accuracy.

That is not true, A-GPS just speeds up the time to fix by supplying ephemeral data via a sidechannel. It just takes longer to receive via GPS if it is out of date or you have moved position considerately since last fix

I have relied on gps with downloaded topo maps in areas where there is literally no cell reception. iPhone X using AllTrails fwiw, I feel like it must have a real gps radio packed in there somewhere.

Indeed it does have a true GPS satelite receiver. Actually, the iPhones are quite accurate.

The iPhone 12 utilizes the GLONASS, Galileo, QZSS, and BeiDou constellations. Utilizing more satellites means determining location more quickly and returns better accuracy especially in marginal environments.

Have you ever used Garmin back in the day, or a USB GPS receiver? It can take a minute or so to get enough initial information to deduce a location at a low datarate. AGPS gets some or all of that information (I'm not sure) from another source, usually a cell phone network so that first location is deduced much faster. Modern phones have GPS receivers, but use AGPS. If a modern phone has no network signal, it will still get a GPS signal, it will just take longer to get the first location.

Not to be confused with other technologies such as skyhook [2], which was used in iPhone 1 and other older devices to fuse radio signal strength, known wifi hotspot locations, etc as a kind of pseudo-GPS. It was only relevant for a few years.

Wikipedia [1] has a nice short explanation.

[1] https://en.wikipedia.org/wiki/Assisted_GNSS

[2] https://en.wikipedia.org/wiki/Skyhook_Wireless

However, without cell service, they fall back to the sky, and the result is usually good to within a few tens of meters.

The downside is that it can take much longer to acquire a fix.