Om's got it pretty dialed in and sewn up in the post as to why AOL and Google are getting hitched.
He's missing though the enemy (AOL) of my enemy (YAHOO) is my friend, which applies to both Google and AOL. So, while I guess you can toss in Microsoft in that enemy model, MSFT would have been a good partner for AOL, and who's saying Time Warner is done dealing!
There are also some very interesting end to end marketing plays here and AOL has in the past been able to do some very innovative marketing deals that have crossed the chasm of the virtual and physical. With the Google directory search and datamining underneath and the AOL sales force, plus already known audience base, the direct marketing implications and 411 capabilities alone are staggaring.
With the phone companies charging .35 cents per 411 call, Google/AOL can charge nothing or a penny, and slam the phone companies in a space they had owned for years.