Hi there,
It could have something to do with the cached settings on the client side...also possible is that the firewall (again on client side) needs MAPI exceptions.
Just a stab in the dark though