We had this issue when I worked in Alaska (56K via sattelite). Our answer was to put outlook in the startup group and force it to open for everyone. (Came at the direction of the agency director)