Hi Stephen,
ListMail uses SMTP for, usually larger, list email. However, welcome and confirm messages use an internal PHP function called mail(). If this function is not operational on your server you might experience the symptoms you describe. Some things that might affect operation of this function are your 'bounce to' (config) and 'send from' (list settings) email addresses. For best results, these addresses should be @ the same domain ListMail is installed on. If this doesn't fix it then you will need to talk to your host about the PHP mail() function not being operational.
Regards