1. does the smtp test in host settings succeed? Ask the Postmaster for correct login credentials for the SMTP server
2. does sending a bulkmail to a single email address entered manually work (using a permitted sender address)?
3. have you checked your email address specified in your own user profile to be valid?

2-Other people. You mean non-DNN installs/staff are having problems sending outside the network? Then the problem is either in the mail server/relay or outside of your network.

I've the same problem : while configuring the SMTP, the test works fine, but when working in the portal, actions that sends notifcation emails fails. For instance when creating a new user, no notification are sent (I can say  that after having made a lot of tests to be sure to understand the issue).

Here is the exception message raised and found in the dnn event viewer:

AssemblyVersion: 04.08.00
PortalID: 0
PortalName: Intranet de l'Ecole Ouverte
UserID: -1
UserName:
ActiveTabID: 54
ActiveTabName: Mon enfant
RawURL: /Monenfant/tabid/54/ctl/SendPassword/language/en-US/Default.aspx
AbsoluteURL: /Default.aspx
AbsoluteURLReferrer: http://intranet.ericpiraux.be/Monenfant/tabid/54/ctl/SendPassword/language/en-US/Default.aspx
UserAgent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-GB; rv:1.8.1.4) Gecko/20070515 Firefox/2.0.0.4
DefaultDataProvider: DotNetNuke.Data.SqlDataProvider, DotNetNuke.SqlDataProvider
ExceptionGUID: cd2a8add-b61d-4c36-8263-a8ad80594c61
InnerException: Mailbox unavailable. The server response was: Authentication is required for relay
FileName:
FileLineNumber: 0
FileColumnNumber: 0
Method: System.Net.Mail.SmtpTransport.SendMail
StackTrace:
Message: System.Net.Mail.SmtpFailedRecipientException: Mailbox unavailable. The server response was: Authentication is required for relay at System.Net.Mail.SmtpTransport.SendMail(MailAddress sender, MailAddressCollection recipients, String deliveryNotify, SmtpFailedRecipientException& exception) at System.Net.Mail.SmtpClient.Send(MailMessage message) at DotNetNuke.Services.Mail.Mail.SendMail(String MailFrom, String MailTo, String Cc, String Bcc, String ReplyTo, MailPriority Priority, String Subject, MailFormat BodyFormat, Encoding BodyEncoding, String Body, String[] Attachment, String SMTPServer, String SMTPAuthentication, String SMTPUsername, String SMTPPassword, Boolean SMTPEnableSSL)
Source:
Server Name: DEDI556

Why is that working when making the test from the  host settings, but not working elsewhere ?