Depends, really. The other companies would have to check their DNS providers, probably using nslookup or something. Firewalls: depends what you have and whether logging is switched on. Spam blacklists would probably give them more sending problems than just to your company, but it's possible. Messagelabs have fairly good logs, if either side is using them.
Basically, if it's not in your Exchange or firewall logs (or anything else between Exchange and the internet), I'd expect it to be somewhere outside your network.
EDITED: 22 Jun 2012 19:16 by PATCH