I'm not sure if I found the culprit and if I did, I just fixed the issue.
However I'll have more time later to play around.

We are using ScriptLogic (SL) which I've never used before and it was the
only thing I could think of that would be causing this problem. I tried it
with a new user and on a different laptop using Outlook 2003, all with the
same results.
There is a place in SL that allows me to set my RPC settings as if I were
doing in outlook itself. Since making the changes in SL, I've been able to
reboot and not lose my settings. I did notice that on the first reboot i
would be prompted for my credentials as normal but once I restarted again, I
would lose the settings as if a group policy or script if overriding my
settings.
We're not using any out of the ordinary group policies so this is only place
that made sense. Tomorrow I will remove myself from the SL service and see if
I have the same issues.
I'll report back in case someone has this issue in the future.
--
Regards,
Jeremy Johnston
I.T. Engineer
CCNA - MCP