[kristopher]

Yes, use DEFLATE[1] before you B64. Also, it does not hurt to up-vote all of these useful comments!

[1] http://en.wikipedia.org/wiki/DEFLATE

[TheZenPsycho]

I tried deflate, and I was surprised, it actually worked in about 66% of the cases I tried. The question remains what to do for those remaining 33%