How exactly do they "return to self-service"? When they initially go to Self-Service how exactly are they launching it, compared to when they return to self-service? Normally, the URL in the shortcut to have auto-login work is the following (where %servername% is your actual web server name):
If they are using a shortcut that they created after logging in, the path may not be quite correct. Other than their shortcut not being quite right, I am not sure why the first time would work and the next time wouldn't. There must be something different in the way they are doing both of those steps.