Sorry, but I'm not getting that.
Why OSCommerce can send email to "email@example.com" and cannot to "@hosteddomain.xxx" ?
Just to be clear the client has just pointed one A Record on my server.
They have their own server for the website and for the email as well.
They are pointing to my server for shop.clientdomain.xxx