Are you using Outlook 2007? If so, what I've found is that the iPhone will NOT accept .ics requests stored on office.live.com (or whatever domain that default option uses). If you setup a free account with iCalX.com, though (or another WebDAV provider), you can upload your calendars there and the iPhone will work with them just fine...you'll just need to manually setup that WebDAV connection in Outlook (same steps, but choose the WebDAV option instead of sticking with the defaults).
Not sure what the problem is, but I just chalked it up to being something to do with the Microsoft/Apple rivalry.