I am using about 530 categories in a test project, and the standard wordpress export did not include all of them.
I found this line in export.php, in function wxr_missing_parents
$passes = 2000 + count( $categories );
and modified it to:
$passes = 6 * (count( $categories ));
...and so far so good. - No idea what it means, but it seems to have done the trick! Thought I should tell someone? :s
P.S. I realise that's an unusually large number of categories, hence it being merely a test project so far ;)