That's weird jwaffe, if the order was 1, 11, 2, 22 etc I'd sort of get it. But yours seems random.
Here's my test, I have 8 pictures named 01,1,2,3,4,22,23,44 ordered in that order in the window. When I highlight them all in "Large Icons" view, right click and select print, they print in that order. Same for details view and all other views.
If I change it to Order by size which puts them in 4,22,44,1,23,3,01,2 they print in size order. So for me it works.
Would you mind using the Windows 7 Problem Step Recorder (PSR) and recreate your scenario again, then paste the results.
To open the PSR, just type PSR.exe into RUN or SEARCH and press enter. When it's open press Start record, recreate your issue and stop record when you are finished. Paste the results and I'll take a look.