One thing you might consider is putting together a script to harvest email addresses from whois records that correspond to the PTR for the querying IPs. Add to that list abuse, postmaster, webmaster, hostmaster, etc @ the poorly run domain. Then fire off a message explaining the situation and that you'll be adding a wildcard record on such and such date (preferably not 4/1). Script all of this and run it every couple of days until the date you gave and then follow through with the wildcard entry. This undoubtedly won't stop all of the whining but you can at least say you tried.
volunteers are welcome to apply for that job.
Perhaps you can get CNet or InfoWorld to pick it and write a story about the service and the impending change.
that, conversely, would be fun.
When it comes right down to it, you've got to do what you've got to do to recover your domain. You provided a service that many of us relied upon. The responsibility rests on our shoulders to keep up with the changing times. 7-8 years is more than enough time for even the laziest of mail admins to update their config. Think about how much bandwidth has been wasted over the years with these errant queries...
about 1 billionth as much as has been wasted by RFC1918-sourced DNS queries sent to the root name servers OR RFC1918-domained DNS updates sent to AS112. therefore i treat it as a personal annoyance but NOT a waste in its own right.