Hi Craig and welcome to our forum,
What kind of e-mail client do they have? In general, you are right. InfoPath needs Outlook on the client to send e-mail. However, you may be able to write some code in the form template to do an HTTP post or something. Another option would be a SharePoint event handler.
Patrick Halstead [InfoPath MVP]
InfoPathDev
Patrick Halstead
Project Manager at Qdabra