His knowledge of the rule's existence is irrelevant. I don't think It was meant to be taken as a limiting boundary on all plans, just good advice that Lucius seemed to trust. And his solution isn't to be merely clever, its to be creative. Harry's point is that a world where evil goes unchecked is barely worth living in, and so there's no real room for compromise. With power like magic that can literally rewrite the laws of physics, no situation is ever really unsolvable if you're creative enough to directly manipulate the rules.