However, when I try and SEND email from my iPhone, I can't. I get a message saying that my outlook server does not recognize my email.
Outlook server is the computer elsewhere on the internet/network that is set up to be an email server. Outlook is the client program that you are using to fetch your mail from the server.
Your Outlook program should be able to display the name of the server that it is talking to. I don't have Outlook in front of me right now, but you'll need to look at your account settings. In your case since you are having problems with sent mail, I suspect the problem lies with your SMTP settings. Verify that they are correct on your iPhone compared to your Outlook client.
Unfortunately a number of email service providers will block SMTP access if it originated from other than their own network. This is to prevent nefarious spammers from using their "post office" if you will as a front to distribute junk mail. But it also means that if you are not on the network (ie, logged on via AT&T's cellular network) that you might not be able to send mail either.
This issue was pointed out as a problem by many people after the phones were originally sold, but I have yet to see a cure for the problem.
The problem is that setting up email accounts in general can be a little tricky, particularly if you aren't that familiar with it. This is not a specific flaw with the iPhone. If you still have problems, find a friend who's familiar with migrating email accounts.
The iPhone does have an "easy" way of pulling over your Outlook client's configuration. When you sync it, go to the tab for email and make sure that the check boxes for the problematic account is selected. It should pull the appropriate configuration info into the iPhone. However, if your service provider blocks external access to their SMTP server you still may need to find a workaround.
Here's a more technical explanation of things with some workarounds.