I think that the trust model for Google Apps account recovery is wrong. The domain name is a separate asset from the Apps account and the data in it.
The owner of the domain name should be able to create a brand-new Google Apps account for it. Recovering access to an account should be done through another channel (secondary email address, SMS, postal mail).
This isn't practical since any Apps admin account has by definition access to modify/reset all regular accounts belonging to that company/domain, so if you don't use things like wipeouts upon whois creation date modifications, the potential to expose a lot of private data from the former owner still exists.
Maybe “account” is the wrong word. I think that the domain’s owner should be able to create an entirely new “instance” of Google Apps (with separate users and separate data), whereupon the old instance would be detached from domain.
An admin of the old apps instance should be able to get into it to access data, delete it, or attach it to a different domain name.
When a domain is being reclaimed by someone signed into a different Google Account than the previous admins, check if the domain's whois creation date has changed, and if so, make it mandatory to wipe out the data previously associated with the domain before continuing.
In addition, password resets via email requested at domains having the whois creation date after the account creation date should probably be disabled.
Google has been pretty strong on encouraging users to enter a "backup" email address. At least, on 4 different gmail accounts it pestered me mercilessly until I gave it one.
Seems like if you are trying to reclaim a domain then requiring the user to verify access to their "backup" email address could be a simple step that would help a lot.
The owner of the domain name should be able to create a brand-new Google Apps account for it. Recovering access to an account should be done through another channel (secondary email address, SMS, postal mail).