I don't know that much about cronjobs so I might be wrong here, but isn't that the same as running php from a command line? In this case it is quite natural that $_SERVER['HTTP_HOST'] is not set as you do not have any http connection with a server. The http_host is some information that is sent in the request headers by the client so unless a script sends such a request, all the server variables starting with http should not be set.
In case you are talking about the send_newsletter cronjob - at least on my local server I get the same error message about the missing http_host variable. But as it still sends the newsletter out (using my local test mailserver, so this might not work everywhere), I did not worry about this error message to much.
Did you use the 'build_list' cronjob before trying to send a newsletter? Otherwise the send_newsletter cronjob does not find any emails to send the newsletter to.
If it still does not work explain exactly what how you create a newsletter and post the whole output of both the build_list and send_newsletter cronjobs.
EDIT: I have just seen your comments at the newsletter contribution. Unfortunately I cannot help you with any mail settings as I do not have the slightest clue about email servers. Sorry /EDIT
David, here's a bit of a long shot: are you trying to connect to an Exchange box via SMTP? I seem to remember that some Exchange machines don't like the EHLO command, and will at that point disconnect whatever client is trying to talk. The newsletter system should use HELO instead when sending email. Then again, I could be talking rubbish - I know very little about Exchange, but a reasonable amount about UNIX mail systems.
Edit: I think actually what I'm talking about only happens if you have a Cisco PIX firewall with smtp_protocol_fixup enabled in the way, so that probably doesn't apply in your case. Never mind! Is there any way you could set up Ethereal or some other packet tracing program to see what's going on at the SMTP port? That might give a clearer idea. Or it might be overkill!