Cannot remove the domain '' because it is referenced by the proxy address template 'smtp:@'

I had this issue on my Exchange server when I realised that my server was incorrectly configured for a few email domains.

Luckily this fixed my issue.
http://www.blogwebsites.net/member.php?page=comments&member=boredazfcuk&newsid=4454

Basically use ADSI edit to delete the offending address from the disabledGatewayProxy attribute.