This problem appears on really fast algos. I made the dup check for this reason when i wrote the blake algo.
The full range is scanned before we get a new job from the pool.... Now, what should we do in this case... Wait but users complains about the low GPU usage
You need to work on your marketing.

Sell it as, "saving power when the network has no work available," or something.
The biggest mistake a FLOSS developer can make is letting users drive development.
99% 99.9999% of users don't have the skills, experience or insight to make development decisions. This is a prime example of why. Of course it is ideal to keep the GPUs pegged at 100% usage. But if there is nothing productive to do, then there is zero sense in burning the watts.
Do what's right and ignore the uninformed, baseless complaints.
And that includes me as a user. Users are just good for feedback on performance, testing, ect. it's usually those that are the most ignorant that are the loudest in their comments/complaints. Ignore them, and if a user asks politely why the gpu isn't 100% just give a simple explanation. If they complain tell them to STFU or fix it themselves.