> The service would give the request a priority value based on the "difficulty" of the puzzle solution.
Seems like single clients could increase the difficulty to higher than what the bot net would do (so it gets priority), and hence get access. Operators of the bot net would probably hard code one value as the difficulty, and it would be lower than what you could typically set on consumer hardware.
Maybe user agents could even do this increase automatically?