It would appear that your exchange server doesnt know that the exchange server at HQ exists. Make sure that both machines are in the same Exchange Organization.
What mrdenny says above is a possibility, however, since it’s to your HQ I assume it worked previously. I would restart the information store and the MTA’s on the two servers (I’ve seen this happen with an information store/MTA going flakey). Also, you might try looking at the routes and having exchange re figure the routes on teh bridgehead servers (Not IP routes, but MTA routes) if you have several servers.