You might have some luck grabbing their DNS records, look for TXT records with the string "spf" in them. If they're a big sender of email, they've likely needed to add SPF records (referencing their transactional email service of choice) to their DNS, in order for their emails to avoid the spambox.
The big companies might be on one of these occasionally, or not so occasionally.
If the subscribe / unsubscribe pages are in the google index, or discoverable, you could crawl those and look for company names and domains on that page, match them up against your db.
Subscribe with a throwaway email address and monitor it for a month or two.
Visit the documentation for MailChimp, Constant Contact, etc. They all have recommended implementation patterns, usually HTML or JS snippets. Parse webpages looking for pieces of those snippets.
Do the same with the most common WordPress plugins for those platforms.