Perhaps 'Mailshield Desktop' is trying to re-deliver deleted email to your SME server when he selects "undelete', claiming to be connecting from 'mydomain.com' using SMTP.
This would produce your situation if his home IP is listed in any of your RBL servers.
You could try this by finding out his current IP, whitelisting it, letting him try to undelete something, and seeing what happens. Or, find out if 'mailshield desktop' can be configured to use smtp authorization when 'undeleting' email.