Ok, after messing with this for quite some time, I have everything working. Here is what I found -
First, the Joomla error messages are not very helpful. I changed the time out error message to indicate the form was being sent too fast. I also changed the local link error message to reflect that the link being sent was not correct. Once you know what the actual problem breaking the send is, it's a lot easier to fix the problem.
The timeout it not a bad idea, but 20 seconds is way too long. Too many people have forms autofilled by their browser or plugins so 10 seconds or even 5 seconds seems more reasonable. A bot will take much less than 5 seconds so you should still be good there. As Mat mentioned, in components/com_mailto/controller.php on line 20, adjust the defined minimum time before sending -
define('MAILTO_TIMEOUT', 20);
The other problem comes in the local link test. Many people seem to think this has something to do with the domain of the sender email, but it's actually it is testing the URL being sent. The problem is that Joomla encodes the URL being sent as a security measure. This is a great as many hosts won't allow URLs in a form parameter to begin with. The problem is that when they started encoding the URL, they do not decode it before testing if the link being sent is a link from within the site or not. Again, this is a very important check, otherwise it would be trivial to send malicious links through your form. The fix is easy. Again in components/com_mailto/controller.php at line 74 look for
$link = MailtoHelper::validateHash(JRequest::getString('link', '', 'post'));
and change it to
$link = base64_decode(JRequest::getString('link', '', 'post'));
Your send email should now work properly without opening up a huge security hole in you site.