Hi. My update which solved it for me. I have used email to my IMAP account on my iTouch via wifi for a year with no problems. I got an iPhone for Christmas (3G and 2.2) and set it up the same and it worked too. However I synched up with Mobile Me and I then started to get the 'Address Invalid' issue. I also got this on my iTouch so I know it is related to this Synch and not related to the iPhone, Wifi or O2.
I changed SSL to off but that did not work. I then did the following and it now works for me:
Settings
Mail, Contacts, Calendars
Select the account
Outgoing Mail Server
Primary Server
Add username to your email address - in full
Add your password
This worked for me, not sure why it worked previously without this but I think it was something Mobile Me did.
Note I used Server Port 587 as I saw that there are earlier issues with the same error, where it seems that many ISPs block spam via port 25 so this can cause issues.
Hope this helps somebody. I am in the UK and use O2.
Guy