Používám to shodně jak ty a myslím, že se data synchronizují vždy tím směrem, kde jsou data méně aktuální. Tak to u synchronizace má správně být. Jediné co mě napadá, zda nemáš v PC či v iPhone špatný čas. Tzn. v iPhone moc dozadu nebo naopak v PC moc dopředu.
EDIT: Teď mi došlo že s tím smazáním by problém mohl být, ale podlě mě se nekontroluje konkrétní datum úpravy jednotlivých kontaktů ale kompletně seznamu. Takže pokud je v iPhone seznam aktuálnější než v PC, kontakty smazané v iPhone by se měly smazat i v Outlooku.