It’s a couple of months past the usual 3-month rule, but I’m bumping this because the Xmas edition of New Scientist has an article on Sudoku that’s alerted me to the fact that a paper by Felgenhauer and Jarvis had produced a definite answer: there are 6670903752021072936960 possible grids. For more details and the paper, see here.
Their method starts off in much the same fashion as my argument above, but where I had to start fudging, they resorted to a bruteforce computer search. The final answer is about 6.6 x 10[sup]21[/sup], so InvidiousCourgette’s friends had a good estimate to begin with (and my upper limit was rather good after all).
9! —>
| 8! →
| | 7! →
| | |
v v v
(9!)**2 X (8!)**2 X (7!)**2 X … X (1!)**2 = big number 
Does this solve the problem?
Nope. It’s trickier than that.