David G. Stork has already explained why the order of filling the cells matters: if you're going to have to backtrack, it's better to backtrack early, and the way to achieve that for Sudoku is to fill in the grid one row (or column or 3x3 square) at a time, so that all the constraints for that row (or column or square) get checked before you start making any unrelated choices elsewhere on the grid.
If you do wish to build up a Sudoku grid in a random order, the way to do that effectively is to not just check for immediate constraint failures after each choice, but to look deeper to make sure that each choice actually still leaves the puzzle solvable.
In particular, I would suggest something like the following algorithm:
Pick a random unfilled cell and set it to a random value.
Run an optimized full Sudoku solver on the puzzle to verify that it still has at least one solution. If it doesn't, undo your last random choice and try some other value for that cell; otherwise, lock in the choice and repeat from step 1.
There are various more or less obvious ways to optimize this algorithm, e.g. by avoiding obviously bad choices and by reusing information from earlier solver runs to speed up later ones. Still, as long as you use a reasonably efficient solver for step 2, even this naïve algorithm should run at an adequate speed. In particular, since you'll never need to backtrack more than one level, this algorithm will always complete a 9×9 grid in at most 9³ = 729 iterations.
Ps. One notable optimization that you may want to make is constraint propagation. That is, every time you set a cell to a definite value, check if that forces any other cells to also have only one possible value. If so, set them to that value and repeat until there are no more cells whose values are forced by your choice. (If you find any cells with no possible values while doing this, then your last random choice is inconsistent, and you can immediately backtrack it.)
In fact, your solver in step 2 will almost certainly do constraint propagation or something similar internally anyway. However, doing a separate propagation step before the full solve lets you immediately mark any cells with forced values as filled, and thus speeds up (and reduces the number of) later iterations.
Another natural optimization is to store for each cell a list (or, more efficiently, a bitmap) of all the possible values it can have (based on the constraints, given the choices made so far) and update this list during the constraint propagation step. This can both speed up the propagation and also let you avoid making obviously bad random choices.
Again, this is also something that Sudoku solvers typically do internally. In fact, since filling up a Sudoku grid basically is the same as solving it, it should not be surprising that, as you optimize this algorithm, it starts to look more and more like a solver in its own right, and you might even start to wonder what the point of calling a separate solver at the end of each iteration really is.
However, it turns out that one important aspect of properly optimizing a Sudoku solver is coming up with good heuristics for the order in which to try different possible solutions, once deterministic constraint propagation no longer helps. Using a separate "inner" solver just to verify continued solvability frees the outer loop to make its choices in any order you want, while still enjoying fast conflict detection by the inner solver.
