The solution is to use the db persisted "remember me" token approach. In our situation, we used org.springframework.security.web.authentication.rememberme.PersistentTokenBasedRememberMeServices.
It turns out that our first attempt at using the db persisted token approach was simply implemented in error. When we did it correctly, it worked fine and solved our remember me problem.