Misspelled Email Addresses - Where do they go?

It depends very much on the email service subscribed to.  As b0lsc0tt says, there is often a Catchall to funnel everything down the pipe to a designated user, but this is not obilgatory.  Many systems now take the policy that anything that is not properly addressed is trashed.  As b0lsc0tt says, rejection is better than trashing.  One company I dealt with recently refused point blank to set up one Catchall mailbox for anything coming in - anything improperly addressed was trashed and not rejected to sender.  I recommended to the client he move to a different email provider that did provide this Catchall facility.

My recommendation to you is to host your own email server, and to have direct SMTP delivery inbound.  It will mean a bit more work, but at least you will be in control.

At first I thought you had a Control Panel to administer your own email boxes.  Having to contact another company to do this for you is even worse!  Presumably you are charged for each mailbox you have.  

Something else to note; typically it can take up to three days for a bouce-back notification to be generated.

Most providers react faster than that in most cases but a few still take a while to generate.

A note to add:
We got rid of catchall in our company because it was getting more spam than legitimate messages with a mistyped address.  Depending on you domain name most mistyped addresses may not even get to catchall because the error is in the domain.  That is the most common error when our customers/clients make a mistake.  If your provider did take three days then you probably would be better off hosting your own mail server.

btw, I would not expect a lot out of HP until you train them ... so it might not be a good first step to count on them only, other than to better enforce that they know how best to run it according to your wishes

b0lsc0tt > We got rid of catchall in our company because it was getting more spam than legitimate messages with a mistyped address

We started to run an upgrade to a spam blocker that sent to trashbin most of the incoming mail to a few valid users, who happened to be important. I think the one configuring the block made one test being something like a few letters and wildcards, not understanding the rules or something. So it caught a lot. Following Murphy's law, it was also the day after they'd got rid of "the catchall" and the affected users happened to be important VIPs. Nothing recoverable.

Let's say, it did not take long to get the catchall running, and the entire anti-spam effort removed, to best ensure the VIPs could get some kind of mail to busy themselves with ASAP

This is the first time I've ever heard of catchalls.  I just figure (mostly because its common practice with all the positions I've held over the years).
NDR is sent back to originating email server stating a failed delivery.

I am a little surprised that the Exec is assessing blame on you guys.  Especially since it was the sender that has the spelling issue.  

Its like being in between a rock and a hard place (bird-brained buyer and enraged executive) :|

Sorry you're in the middle of it.

Regards,