This is a very easy mistake to make: you configure your cache keys in one place, and process requests in another. With nothing linking them it's not at all surprising for them to be out of sync.

As for whether it requires it's on domain, domains are cheap and publicity gets people to pay attention to problems and fix them.