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...