We've just setup a fresh SBS server 2008, and several windows 7 workstations all woth Outlook 2010 installed. When we initially set each PC up they worked fine discovering exchange autofilling the username in and connected as you would expect. the following day each machine was asking for a password upon opening Outlook and upon sending and recieving, we also had the same issue with outlook on the server itself.
They were on a dynamic WAN IP address which has now been set to Static and we've reissued the self certificate and it seems to have fixed the issue with Outlook on the server... however the machines are still the same.
I have also tried disconnecting a machine from the network and reconnectin/resetting up Outlook but still have the same result.