Wow! You sure posted a lot of problems. But I think I know what's up with this one. There are a couple of possibilities (see links below) but I think it's most likely the first link.
RE: First link. A sender will receive an NDR if they try to send to a disabled account. That's really easy to fix. Just go to "Active Directory Users & Computers", open the disabled account. On one of the Exchange tabs (I forget which one, might be "Exchange Advanced"), you'll see "Mailbox Rights". Click that button and add "Self" to the mailbox. Give it "Full mailbox access" and "associated external account" (or something like that.. it'll have the word 'external' in the name). Click 'apply' and there won't be any more errors for that account.
If you have other disabled accounts, I don't know of a quick-n-easy way to find them other than opening each and every OU and looking to see if it has a disabled account. We started adding "- Disabled 00/00/00" (where 00/00/00 is the date the account was disabled) to the end of the user's description then moving the disabled account to a "Disabled" OU to make all of them easy to find.
Let us know if that didn't fix your problem. Also, if you have an error message, give http:\\support.microsoft.com a try. That's a lot faster than waiting & hoping that someone will reply here!
I actually just had someone call with the same problem. An external e-mail account he used to e-mail to all the time was giving him the same error:
"You do not have permission to send to this recipient". I followed the steps you mentioned above, but I'm curious; does that simply stop the NDR from getting returned, or will he acutally be able to send to these people now? He needs to be able to send the e-mails out.
Rsteph, I'm confused. You say the email account your user sent to was external? Then how can you set permissions on an external email account?
Anyway, your question was (to paraphrase): if you grant "self" permission to the mailbox of a disabled account, what happens when someone sends a message to that disabled account? Will the sender get an NDR back (like they would if you didn't grant "self" permission) or will Exchange simply deliver the message? It will simply deliver the message.
So, that might be something you want to consider when disabling an account. #1 - granting "Self" permission to the mailbox. And #2, that the mailbox, in the meantime, will continue to receive messages. We have a lot of students who work for us in the summer then when fall rolls around, they go off to college. Sometimes, they come back the next summer. Instead of creating, deleting, creating, we disable-reenable their accounts. But when we disable the account, we also remove them from any Exchange mailing lists too so their mailbox doesn't end up with tons & tons of messages. And we add a little reminder about what lists the person was a member of in the description or comments of the account. And the date that the account was disabled because, well, Personnel often never tells us when an employee is gone. I had accounts that hadn't been active for 3 years. So once a month, I look for accounts that haven't been active for 90 days and disable them.