Descobri eu mesmo. Felizmente, o Firefox ainda é altamente personalizável via CSS. Então eu criei um userstyle que faz o trabalho. Você pode alterar a ordem de outros elementos também.
@namespace url(http://www.mozilla.org/keymaster/gatekeeper/there.is.only.xul);
#FindToolbar .findbar-closebutton {
-moz-box-ordinal-group: 0 !important;
}
#FindToolbar label {
-moz-box-ordinal-group: 0 !important;
}
#FindToolbar textbox.findbar-textbox {
-moz-box-ordinal-group: 1 !important
}
#FindToolbar toolbarbutton.findbar-find-previous,
#FindToolbar toolbarbutton.findbar-find-previous label {
-moz-box-ordinal-group: 3 !important
}
#FindToolbar toolbarbutton.findbar-find-next,
#FindToolbar toolbarbutton.findbar-find-next label {
-moz-box-ordinal-group: 4 !important
}
#FindToolbar toolbarbutton.findbar-highlight,
#FindToolbar toolbarbutton.findbar-highlight label {
-moz-box-ordinal-group: 5 !important;
}
#FindToolbar checkbox {
-moz-box-ordinal-group: 6 !important;
}
.findbar-find-fast.findbar-find-status,
.findbar-find-fast.find-status-icon {
-moz-box-ordinal-group: 7 !important;
}
Parece que o OSX sofre do mesmo problema, por isso existe uma versão separada para usuários de Mac.
