File in root directory
Don't discard the possibility of putting a file in a root directory of the corporate website. It works well and is widely used: Google Webmaster Tools is one example of such technique. This makes this approach attractive: since most users already know it, they won't be lost. Also, it doesn't require any technical knowledge, unlike modifying MX records (most small companies won't even know what an MX record is).
In order to avoid polluting the root directory, you should ask to put a file only when doing your checks. Once you've found the file, the user may be able to remove it.
Note that users who don't have any corporate website won't be able to access your service, but I don't think there are many customers in this case.
You should check for both http://example.com/file and http://www.example.com/file, because some websites are configured in a way they don't support http://example.com/ form.
You may support HTTPS as well, given that I don't think there are a lot of companies with no redirection from HTTP to HTTPS.
You should not accept any other third-level domains such as http://mysite.example.com/, because this will make it possible for someone who bought an third-level domains to claim that he's the owner of the second-level domain example.com.
Sending an e-mail
Sending an e-mail with secret link is rather problematic. You can't do it to firstname.lastname@example.org, because a given person may not have a corporate e-mail address (this is often the case of startups, where people prefer using their personal address).
Using e-mails such as email@example.com will not work in some cases.
First, there are always companies not having firstname.lastname@example.org, email@example.com etc., but having their particular "system" e-mail addresses you haven't whitelisted. Consider specifically foreign companies; for example, in France, it is not unusual to use "Administrateur" instead of "Administrator", including for e-mail addresses and account names.
Second, many small companies don't access and don't know how to access their system e-mails. They pay not even know they have firstname.lastname@example.org with hundreds of urgent e-mails waiting for their reply.
For the same reason, you can't base yourself on WHOIS records for e-mail address.