Base64 Decoding breaks when encoding leads with +

+ is one of the regular base64 characters, used when the 6 bits being encoded have a value of 62.

My guess is that you're putting this in the query parameter of a URL, where + is the escaped value of space. For that use case, you should use a URL-safe base64 encoding instead:

Using standard Base64 in URL requires encoding of '+', '/' and '=' characters into special percent-encoded hexadecimal sequences ('+' becomes '%2B', '/' becomes '%2F' and '=' becomes '%3D'), which makes the string unnecessarily longer.

For this reason, modified Base64 for URL variants exist, where the '+' and '/' characters of standard Base64 are respectively replaced by '-' and '_', so that using URL encoders/decoders is no longer necessary and have no impact on the length of the encoded value, leaving the same encoded form intact for use in relational databases, web forms, and object identifiers in general. Some variants allow or require omitting the padding '=' signs to avoid them being confused with field separators, or require that any such padding be percent-encoded. Some libraries (like org.bouncycastle.util.encoders.UrlBase64Encoder) will encode '=' to '.'.

Exactly which path you choose here will depend on whether or not you control both sides - if you do, using the modified decodabet is probably the best plan. Otherwise, you need to just escape the query parameter.

Example below, this string was encoded but can't be decoded.

+ueJ0q91t5XOnFYP8Xac3A==

That's not true, in itself:

byte[] bytes = Convert.FromBase64String("+ueJ0q91t5XOnFYP8Xac3A==");

works fine... suggesting that it's the propagation of the string that's broken, which is in line with what I've said above.