"Just like they have policies on deleting received emails"
Actually the laws state otherwise, companies must have a retention policy to ensure mails are kept for a given period.
And how often keys should be published? Every day? Every week? Every month? Every half a year? Every year? Every five year?
There could be always a windows where leaked/stolen email can be verified. Criminals will just need to be quicker. If you can get the messages when a key is still valid you can timestamp them - even with GnuPGP.... - to show they aren't tampered with.