It definitely seems like one needs to pare down the interactions with the provider to some bare minimum. Limiting it to single, uncorrelated map-reduce (or even just reduce) steps seems like it would remove a lot of potential for abuse.
But who knows---if service providers tend to take in and operate on more data than clients (especially from multiple clients), it seems there is a fundamental information imbalance, and obfuscating techniques by clients can't possibly do as well as deanonymizing techniques by the provider in the long run.
I wonder if it is the case that fully homomorphic encryption might _increase_ the potential for such information leakage relative to a partial homomorphic encryption; the more algebraic structures for which an encryption function is a homomorphism the more vulnerable it is. If a fully homomorphic encryption captures the +, * operations of a ring, you can exploit two identity elements, one for * and one for +. The next step in 'badness' would then be something like R-modules, where in addition to the ring you have another group (and another operation and identity element).