Using Outlook 2010 I have no problems saving phone numbers with + and country code (+1 for USA & Canada, +49 for Germany and so on). As far as I can remember Outlook 2007 it also accepted + and country code in contacts?
If not, then simply use 00 instead of +. Both work as prefix to country code so a phone number can be told and dialed using both, for instance +1 202 456 1414 or 001 202 456 1414 for a certain residence in Washington, D.C, and +49 30 2000 2021 or 0049 30 2000 2021 for respective residence in Berlin.
Kari