What about deterministic padding? As a (badly thought through) example: Hash the plaintext, then use the first couple of bits of that result as your padding size.

This should counteract averaging of requests. On the other hand, an attacker might work around this by adding a unique token in addition to their guess...

Yeah, the important part is to randomize the output itself, in addition to padding. Even without the padding it makes for a significant challenge to determine just where your known plaintext is to compare from. But with enough attempts, if deflate eventually succeeds in shortening a message on a successful match, you could eventually find the matching message. Like you say, probably too long to be effective (depending on the number of random permutations and the size of the secret)