Wow, Stevie, you've never seen large data tables? : ) Heh, come see our insurance bonus/malus tables : )
Firefox, simple, sucks donkey butts trying to print anything that's not plain text. Really. It can't print forms, and it can't print tables. It's likely starting your tables after the second page because it can't see a place to break it, so moves on to the next page. Just like it does with fieldsets. Firefox ALWAYS starts a fieldset with more than a question in it on the second page. We have a fieldset with just 5 questions on it... starts on the second page. Paper waster.
ALL THIS FANCY CSS TRANSITIONS AND HTML5 BUT CAN IT PRINT??? WILL IT BLEND?? No, Firefox won't blend, and hasn't since... like, Mozilla. Heck the float-print bug is from Netscape 6 or something.
Here is the bug and a possible solution might be, if there's text before the table (headers, captions...) try display: none to see if that at least stops the cutting off of the first two rows. Try to make sure overflow: visible is stated in the print stylesheet.
Join the 21st century, throw away your layout tables and you'll find printing becomes a whole lot more fun.
Nah, backwards browsers are backwards no matter how futuristic your code.
I never found a solution to the problem with fieldsets (other than warning people on the site that if they have firefox, they don't want to use that browser to print... and they get suggested to use the PDF format we have instead).
You may also want to consider offering the tables in PDF if that's possible. This was our solution.