you are correct, what version of Outlook are you using. when you recreated the outlook profile did you ensure old OST files have been deleted.
Also ensure you have all necessary service packs & roll up packs installed for outlook on the affected machine