* TeleAtlas, which is in bed with Google
* Navteq, which is owned by Nokia, which has a deal to provide maps to Bing
So now maps is one of the few areas where both Google/Android and Microsoft/Nokia have a blatant advantage over Apple. Why would they want to give that up?
What Google does have is that they partner with whomever has the best available information in the area of interest (check out the copyright info when you scroll around the world on google maps on the web) and augment that with streetview, Yellow Pages, crowdsourced info from Android, etc (and vetted by hand)
It also strikes me that Apple Maps do not have a web interface (unless I'm wrong). In my experience, anytime something I care about in my neighborhood is misplaced on Google Maps, I use the web interface to correct the location. Without this ability, I imagine that it could take Apple a long time to reach parity with Google Maps.
As they say, the enemy of my enemy is my friend -- partnering with Apple would boost their Bing Maps market share into double digit percentage growth, all the while taking Google's map market share down. Even if you know the relationship won't last long and that in the end you'll have another competitor in the space, the rewards far outweigh the risks.
It's far better to take down the king and fight for the throne than to always be a peasant.
There really aren't any major "alliances" right now. It's a mess.