Most sophisticated sudoku solving algorithms, including mine, do not assume the grid has a solution or one solution. They test and give all possible solutions. I am really trying to solve an NPC problem.
That said, your comment still tells me something I do not know - you seems to say that given a sudoku that is known to have one solution, there may be polynomial algorithms. This reminds me of someone who left a comment in my blog, saying that if the solution is unique, at each step there are at most two choices with the exact cover matrix. He couldn't prove that, but his program run happily on tens of thousands of Sudokus without problems. This does not necessarily solve sudoku in polynomial time, but may make solvers faster for unique sudokus.
About the complexity of Sudoku which is known to have a unique solution: I didn't say there is a polynomial algorithm for it. It's equivalent to the Unambiguous SAT problem, and Valiant and Vazirani proved that it's in some sense almost as hard as the SAT problem itself. You can't call it NP-complete (because that's not known), but if there is a polynomial algorithm for it, then there is a probabilistic polynomial algorithm for every problem in NP; and since you can run a probabilistic algorithm as many times as you want and get independent results, you'd be able to solve every decision problem in NP with immense certainty (although less than 1).
About efficient algorithms for Sudoku, I think that the crux here is average case complexity (defined in some way over the sort of samples you are using). It's not clear to me that average case complexity for Sudoku is high, at least for the kind of puzzles we know how to generate. Certainly solvers based on backtracking seem to handle them very well. It's very hard to prove results about that, though. In any case, if someone has a polynomial time algorithm for Unambiguous SAT, or something equivalent to it, that would pretty amazing (but I doubt it - the average time might be very good, though).
While this is not NP-hard under the usual definition, modern complexity theorists believe derandomization to be possible to a degree similar to their belief that P is not NP.
Moreover, once you define NxN Sudoku (the generalization is easy), you need to pick the problem for which you want to prove a hardness result. The decision problem is typically defined as "given an instance of a problem, determine if there is a solution". For Sudoku, you would need to decide if a partial grid can be completed to a full grid, i.e. if the given puzzle is solvable. This has been proven to be NP-complete. However, this is not how the puzzle is usually done, including in this benchmark: you are given a puzzle which is known to have a solution, and the solution is known to be unique. You then need to find the solution. It's been shown that such a Sudoku problem is equivalent to the unambiguous satisfiability problem (given a logical formula which has a unique variable assignment that satisfies it, find that assignment). Now the unambiguous satisfiability problem is not known to be NP-complete when phrased as a decision problem.
Anyway, don't just throw around terms like "NP-hard". :)
EDIT: edited "unique satisfiability" to "unambiguous satisfiability". I believe this is the correct terminology for the "promise" version of the problem which I described, and to which Sudoku is equivalent. (The unique satisfiability problem is "decide if a logical formula has exactly one solution", where you are not told if it has more than one, none, or just one).