Also, if we do delete their mailboxes will anyone who sends an e-mail to that address receive an automated message that the e-mail address is no longer a valid address?
A: Yes, to both your questions. You can delete a mailbox from the Mailbox listing in System Administration. If the mailbox is deleted, anyone that sends to that address will get a message that says something like "That mailbox does not exist" (the exact message comes from their own mail service, so it will vary).
Here are a couple of options that you can also consider for handling any emails that might still be going to those old addresses:
1) Unchecking the Allow Relay checkbox in the Edit Mailbox dialog will make it so that email cannot be sent from the mailbox any longer, preventing anyone from accidentally replying from that address.
2) Adding a Mailing List entry that is the mailbox name you don't want active is a way of forwarding incoming e-mails to another mailbox, so that they are still received, but in another mailbox.
3) You can put an Out of Office Rule on the mailbox to send a friendlier message, such as "If you need assistance please contact ...". In that Rule, you could also uncheck the "Store Message" option, which tells the Rule to not actually save the message after the response goes out.
4) If you are going to delete a mailbox, you probably want to save all the e-mails in it first for future reference -- use the "Export the entire mailbox to an archive, do not delete any messages..." option in the E-mail Archive Wizard. This will save all of the e-mails (old and new) to an archive file that you can access later if needed.
5) Also note that you can use the Mailbox Permissions to give anyone else in the company access to those mailboxes, so that they could a) respond to emails as necessary, b) keep the history of what was sent and received, and c) move any emails they want to keep to any of their other mailboxes.