I was in the middle of a migration from Exchange 2003 to 2010 and was troubleshooting public folder replication when I noticed my replication emails to the new public folder database were stuck in the unreachable messages queue.

The solution is to simply restart the SMTP service:

net stop smtpsvc
net start smtpsvc

Then the messages flowed out the appropriate connector.