Well, the issue is that when I ask the relocation server for a validity of a certain cert, it gets my IP.
Yes, back when OCSP was designed, that didn't seem to be a big deal. Wallets don't use it anyway.
You could theoretically design a new version of OCSP that used oblivious set intersection, so although the server would see your IP, it would not see what your query was and thus would learn nothing beyond "someone behind this IP wanted to know the status of some certificate", which isn't a very useful piece of information to have. Or you could query via Tor, etc.
But as I said, revocation is rare. Browsers just have a hard-coded list, and wallets would probably end up the same, if they ever needed to revoke a cert for some reason. Then there's no server at all. Nice and simple.