Just knowing that the domain is legit is way better than what we've got now. If they're excessive then you can just block the entire domain and just have exceptions for people you want.

The switch over from telnet/rsh to ssh happened reasonably quickly and without incident because as you said it only affected your own users. If they wanted to connect then they would have to get a client or just not connect anymore. Also people that would be using telnet/rsh with your hosts would be authorised users and you'd know who was who and who should have access.

As to the ratio it depends really. For my personal email then an occasional blocked email isn't that important so about 80%-90% correctly delivered really. You could log attempts but you're still wasting time looking through the list to make sure you've not lost anything important.
The difference between personal where lost email isn't major against business where lost email could be lost income is the big point here. I know people that use Hotmail and have the exclusive option set in their spam filter which only allows addresses from the address book to be delivered.

It's an interesting point to make. How much lost email are you willing to put up with to ensure that your spam fighting works?