However, it seems Norvig was feeding his program with all three types of puzzles -- zero, one, and multiple solutions -- so perhaps that led him to implement a more robust search.
But a propagated constraint isn't always just a single value at a time. There are cases where a solver (human or machine) needs to identify that a group of two or three or more cells mutually creates a constraint. ("Naked twins" and other such configurations, in Sudoku jargon.) Which can recursively cause to exist another such mutual constraint, and so on. Identifying every possible way such a constraint can arise isn't a simple operation either to implement or to execute, computationally speaking.
For both Norvig's programmatic solver and for a human, it's possible and common for trial and error to be faster and more expedient than trying to identify and execute every possible means a constraint can arise. Norvig's aim was for implementational simplicity more so than computational elegance, deciding to care about only the simplest possible type of constraint, and let trial and error handle everything else.