What causing this "Invalid length for a Base-64 char array"

After urlDecode processes the text, it replaces all '+' chars with ' ' ... thus the error. You should simply call this statement to make it base 64 compatible again:

        sEncryptedString = sEncryptedString.Replace(' ', '+');

I've seen this error caused by the combination of good sized viewstate and over aggressive content-filtering devices/firewalls (especially when dealing with K-12 Educational institutions).

We worked around it by storing Viewstate in SQL Server. Before going that route, I would recommend trying to limit your use of viewstate by not storing anything large in it and turning it off for all controls which do not need it.

References for storing ViewState in SQL Server:
MSDN - Overview of PageStatePersister
ASP Alliance - Simple method to store viewstate in SQL Server
Code Project - ViewState Provider Model

My guess is that something is either encoding or decoding too often - or that you've got text with multiple lines in.

Base64 strings have to be a multiple of 4 characters in length - every 4 characters represents 3 bytes of input data. Somehow, the view state data being passed back by ASP.NET is corrupted - the length isn't a multiple of 4.

Do you log the user agent when this occurs? I wonder whether it's a badly-behaved browser somewhere... another possibility is that there's a proxy doing naughty things. Likewise try to log the content length of the request, so you can see whether it only happens for large requests.