Mailbox Not Found, invalid mailbox, User unknown, not our customer: these are all saying pretty much the same thing. In the "firstname.lastname@example.org" bounce examples above, the mail server "example.com" doesn't have an account for anyone with the email name "someone". A couple of common reasons:
Mailbox full, or Quote Exceeded: sometimes this will show up as a part of a "Mailbox unavailable" message. It's fairly clear, though: your recipient has too much email and their server isn't accepting any more. This is most common with web-based email services like Hotmail or Yahoo, which have limits on how much mail you can accumulate. This can also be a sign of an abandoned account - someone's stopped looking at and cleaning out the email. In any case, you'll need to try and contact your recipient through some other email account, or some other way.
Host unknown, Domain Lookup Failed: this means that the mail server you're attempting to use, the "example.com" part, in the examples above, doesn't exist. A common reason is again, a typo on your part. Make sure you typed it in correctly. Another reason are ISPs that change their name. The largest example of this in recent memory has been "attbi.com" changing their name to "comcast.com". Anyone trying to send to an old "attbi.com" email address might get this message in return.
Unable to Relay: this is a terribly obscure error message, but also becoming more and more common as ISPs try to crack down on spam. Mail is sent by relaying email from one server to the next. There could be many servers involved, but typically it's the mail server at your ISP relaying your email to the mail server at your recipients ISP.
In general, a mail server must "know" either the sender of an email, or its recipient, in order to safely transmit mail. Mail servers that do not enforce this requirement are called "open relays" and can be exploited by spammers to send out tons of spam.
Things get complicated because not all ISPs agree on what it means to "know" the sender of an email. All of these might result in an "unable to relay" message, depending entirely on the servers and ISPs involved: