How can I sort the order of status messages?
$variables['display'], passed to the theme function is optional, and its purpose is only to limit the type of messages being shown; for example, if its value is "error," only the error messages should be shown. The list of messages is returned from drupal_get_messages(), which should be called as drupal_get_messages($variables['display']).

To answer to your comment, you can avoid duplicating all the code used by theme_status_messages() if you follow these steps:


obtain the array of messages from drupal_get_messages()
sort the obtained array of messages
use the array to set the content of $_SESSION['messages'], which is the session variable used to contain all the messages set from the modules
call theme_status_messages(), passing the same argument passed to your theme function (not the array obtained from drupal_get_messages())


This method seems half of a hack, to me. What happens if Drupal would change how the list of messages are saved? It could be that future Drupal versions will not use a session variable for this purpose.
It also take the assumption that other modules didn't override the theme function, but it would be easy in the implementation of hook_theme_registry_alter() to save the previously defined theme function, and call that function instead of assuming that function is theme_status_messages().