The problem is that the client doesn't trust the relay.  If you are the relay, and you are an evil relay, you probably aren't going to be stripping off any IP addresses.  We need a solution that proves to a client that they aren't exposing their IP address to a relay.

But of course the way to do this is to use a VPN or tor.

If tor is totally unusable than we need to make a new tor. That sounds like a huge project, so I'll bow out and leave it to the rest of you.