Thinking about this more, an easy solution for the tracking fears would be to replace this cache the phone creates for AGPS with pieces of the database directly from Apple when syncing/updating the phone. It could do a quick location update, and seed the database with information in a 100-200 mile radius. Not sure how large the DB would be for that, but the size could be adjusted to still maintain quick performance. Maybe even let the user pick a general area, for frequent travelers.

Not sure if Apple would be willing to do this though, since the master lists for WiFi access points are quite valuable. Skyhook's sole purpose for existing is to generate these lists, and sell access to them.