Solved it, a few hours after posting this question, after struggling with this for a couple days!
The problem had nothing to do with my computer, and was caused by the person typing on it! Subconsciously, I was typing "www.our-domain.com", and all of my coworkers have been typing "our-domain.com" the entire time. We didn't have Apache rewrite rules in place, so at login, the session ID was being set in a cookie with the "www." as part of the domain, but the redirect for the callback function had an associated url without the "www.", so my browser was using two different cookies, which I somehow didn't see until now (because the way I was searching for cookies also included the www!). Very simple, and should have thought of it earlier. Moral of the story: be careful about subdomains with your sessions.