I neglected to mention this problem is on a WML site, so all visitors are using a mobile. 😉 I like the survey idea for some other HTML sites. I'm thinking that the frame will state the page wasn't found but something is displayed below, and ask for feedback if it is close enough or not. If not, then off to a search or home page.
The story is very different on the WML side. Only two URI's have changed and those were forced due to an ISP/carrier stubbornly caching a very old version of the page. A rewrite takes care of that. The major problem was spelling:
dls -> dis, Dis, Dls
index.php -> Index.Php, ind, Index, index
.php -> .ph, .pgp, .pip, .hp
The other problem was linking to pages that shouldn't. Well, the IQ level of a vast majority of WAP/WML site owners rates pretty darn low and for some reason they linked directly to an "offline" notice that was displayed when a service was off for a month. Why? 😕 Not a clue! Someone even managed to link directly to my error pages, which of course redirected to the home page! Thanks to the style guides posted by Weedpacket, among learning other things, I have discovered the joy of 410. "The URI is dead! Long live the URI"
As a related aside, people were hotlinking to my content. Solution: referrer, move content out of webspace, AND copy content to and deliver from a randomized directory (e.g. /download/alsdkn229fgks/picture.jpg), cron job to clean up every 5 minutes. Then I discovered hotlinking to my THUMBNAILS (damn those unethical dirtbags)! Solution: cron job, rename thumb directory every 1-6 hours. Now I can add what I consider as "giving the finger" to those sites: 410.
From your ideas and references, I have gone for the middle path: combination of rewrite, 404 and 410. Thank you Brett and Weedpacket.