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).
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.
In addition, password resets via email requested at domains having the whois creation date after the account creation date should probably be disabled.
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.
In addition, expired domains purchased by someone else won't be usable with Google Apps.