EDIT: Original suggestion which apparently doesn't work
I'm sure the reason is that it thinks it's a query parameter called Key. Could you make it a parameter, with that part being the value, e.g.
www.example.com/Find?Route=Key=
I expect that would work (as the parser would be looking for an & to start the next parameter) but it's possible it'll confuse things still.
Suggestion which I believe will work
Alternatively, replace "=" in the base64 encoded value with something else on the way out, and re-replace it on the way back in, if you see what I mean. Basically use a different base64 decodabet.
Alternative suggestion which should work
Before adding base64 to the URL:
private static readonly char[] Base64Padding = new char[] { '=' };
...
base64 = base64.TrimEnd(Base64Padding);
Then before calling Convert.FromBase64String() (which is what I assume you're doing) on the inbound request:
// Round up to a multiple of 4 characters.
int paddedLength = (4 - (base64.Length % 4)) % 4;
base64 = base64.PadRight(paddedLength, '=');