Apparently our domain has been spamlisted, and a check has revealed that we're an open relay.
Internally we have just one mail server, Exchange 2007. No edge transport.
Send connector is configured with Address Space *, cost 1; FQDN same as our MX
Default Receive Connector is same FQDN; authentication is basic only, permission groups are anon, exchange users, exchange servers, legacy exchange.
I don't know how to troubleshoot beyond this.