Yes, I can simulate something which may be what you are seeing.
A1:A5 contain the values 1;2;3;4;5.
If I sort descending then I get 5;4;3;2;1. That's okay.
However, if I hide a row - say row 2 - and then sort descending, the hidden row is excluded from the sort. I get 5;2;4;3;1 and the 2nd row remains hidden.
I see this in both XL 2002 and XL 2003.
This behaviour is confirmed on this MS Help & Support article:
XL: Sorting Feature Ignores Hidden Rows
I don't have XL 2007 at work so I can't check it. The behaviour could be different in XL 2007 because sorting was overhauled (a new sort object was introduced).