As you don't tell us your Outlook version, try this:
Tools-Account Settings - (highlight the account) -Change-More
settings-Outgoing Server and check the authentication box...Your new ISP
obviously requires authentication. Did you not read the settings properly
when you changed?
They are emails i'm sending. I dont know how to authenticate the SMTP mail
host in Outlook. I never had messeges like this before. It accured since I
switched provider last week.