I made a Query for the datasheet, sorted that, exported, and it still doesnt work.
Well, I was going to suggest this exact step until you said you had tried it...
OK, when all else fails, only two possibilities remain. One, your machine needs to be seen by GhostBusters. Two, you are not exporting from where you think you are. I can't help you with the first case, but I
can give you a hint for a brute force method to fix the second case.
Create a new table that exactly matches the field descriptions of the original table, but create it empty. Set up the primary, secondary, tertiary, whatever-ary keys you need to assert the correct export order. Then run an append query that loads this new table for your old table.
Now try to export that new table that has totally different keys. See if that does the trick.