It's pretty common these days for mail servers to require SMTP authentication. The problem is that the CFMAIL tag has no place for a username and password when sending mail. Not to worry, you can use the "username:password@mydomain.com" syntax in the "server" attribute of the tag to authenticate. For Example:
You can also use the same server syntax in the mail server text box in CF admin. If your server doesn't use SMTP but uses "POP before SMTP" you can solve that problem by hitting a mailbox first with CFPOP then sending your mail. Dan Vega has a great explanation of that technique.