The solver doesn't obviously negate the puzzle's NP-completeness. It first reduces the solution space, then starts brute-forcing what's left. I don't have a proof on hand, but that just smells nonpolynomial.
You could argue that, if we consider "Sudoku" to be the instance of the puzzle where n=9, then the puzzle isn't NP-hard because it has the constant-time solution of trying all 6.67e21 solutions, but the result is so uninteresting that it's understood that the author means the more general problem.
Depends on the initial state of the puzzle. Sometimes there's always a deterministic set of correct next moves to make. I guess this refers to cases that aren't like that?
Right; we're talking about upper bounds here. Assume that the boards are chosen by some kind of wily, malevolent demon with an obsessive desire to embed tricky 3SAT problems in everything.
Similarly, sometimes your sorting algorithm takes linear time because the input was a sorted list. That's the lower bound, but lower bounds usually aren't as interesting as upper bounds.
You could argue that, if we consider "Sudoku" to be the instance of the puzzle where n=9, then the puzzle isn't NP-hard because it has the constant-time solution of trying all 6.67e21 solutions, but the result is so uninteresting that it's understood that the author means the more general problem.