"Unfortunately, there is not much we can do at this point since the data has already been compressed as much as possible and no matter what we do we have that 8000 byte limit."

I hope you'll excuse my blatant self-promotion, but you can go much further than this for UDAs -- and I explain how to do it in the SQLCLR chapter of "Expert SQL Server 2005 Development" ... (which you can find here: http://www.amazon.com/dp/159059729X )

And while I'd appreciate it if anyone who is really serious about this topic buy the book, I won't make you spend your money just for this solution. So if you're interested (reply here if so), I will post a followup in a few days. In the meantime, I think this is a good puzzle, so try to solve it yourself first. Here is a hint:

Think about how to leverage the fact that you have a runtime environment at your disposal. Focus on garbage collection. By using this compression method, each uncompressed value will have to be garbage collected twice: once for the value passed in from SQL Server, and again for the value decompressed/deserialized from the compressed/serialized stream. Is it possible to set this up so that each value will be garbage collected only once?