I thought this was the default behavior in Exchange 2010 but apparently it is not - how can I ensure that when I mark a mailbox for removal in Exchange 2010 console, it will remove all instances of that recipient from any distribution lists? Right now, it removes the mailbox, but retains the member, causing "bounce" messages when people send to that mailing list.
That's the "intended" behavior of static distribution lists. You have to either join and unjoin people manually, or create a script to do the work for you. Powershell is your friend if you do a lot of this kind of thing.
Alternately, you can move over to dynamic distribution lists, which would update themselves when you delete a user, but those have their own set of problems.
I’d think the easiest solution would be creating a delete user script that scans your distribution lists for user being deleted and removes that account.