For what its worth, you can still call AOL on the phone if you get locked out of your account, and they still have millions of users. As someone who's helped people with their locked out AOL mail accounts before in the last five years, I can easily state that AOL is a superior customer service experience over Google.

(Mind you, case can be made that Google's lack of the same makes the account more secure.)