Isn't the obvious 80% solution a separate cookie that just says "this browser last logged in using service X" that the server can use to give UI cues?
how would you suggest your customer which login to use the first time she tries to sign in on another device?