le strade sono tante, innanzi tutto contatterei il server per verificare se hanno installato un MTA tipo sendmail o se hanno intenzione di farlo, se ti dicono che non c'è e non ci sarà neanche in fututo hai diverse strade, puoi usare le funzioni di PHP per autenticarti al tuo ISP e inviare da li, puoi usare le funzioni IMAP per inviare da una casella IMAP .... oppure naturalmente puoi anche cambiare server