They can't be without a category because if they were they would never show up on your blog. Or at least IF they have no category that is what will happen.

So if you are talking about posts with only one category, or more to the point talking about deleting a category that has posts that use that cat as the main cat, I think they will go up one level OR to the next lower category number.

If you delete a cat that has never been used as a post's main category then it just deletes the cat and removes it from the sub-cat on any posts that used it that way.

But I've never tested this! Your installation is way too big to backup your database and delete a category to test, but that's an idea you might consider. Backup using phpmyadmin's "backup" feature, delete a category and see if evil things happen or if it works the way you wanted. If evil things happen you can (a) blame it on Obama and (b) use phpmyadmin's "backup" feature to restore.

IF you do that I highly suggest you basically delete all your hits by deleting a day's worth at a time on your hit summary tab.

Much easier and less risky to make another installation and set up the conditions you want to do, then see what happens there eh?