I have a similar issue and my provider is not prepared to do anything about it. They say the webserver is not meant for sending mails.
I've configured SMTP in Joomla's global options, but uddeIM doesn't seem to use it. Is there an easy way to use SMTP in uddeIM too?