Sorry, but Show All, Show Omitted Only and performing a new find have always unsorted the records in the resulting found set. This did not change with FileMaker 12.
I'm having the same problem with FMP13 Adv.
No one at FileMaker see's this as a problem that needs attention??
Seemingly not since the problem has now spanned a minimum of 3 versions!
As far as I can tell, and I've used FileMaker products since FileMaker 2.5, this has always been this way. Performing a find or selecting show all records produces an unsorted set of records. There has been no change in this behavior. It's quite simple to select Sort Records after doing one of these options manually and it's equally simple to do the same in a script by adding a sort records step after the perform find or show all records step.
As a fix, you can make a small script that fires OnModeEnter:
If ( Get ( WindowMode ) = 0 //Only in Browse Mode )
Sort Records [No Dialog]
The Sort Records - script step without any sort order specified, will allow FileMaker to apply it's last known Sort Order for that layout...