Da kann ich auch nur zustimmen, dass der Optimizer da eher pessimistisch als optimistisch vorgeht.
Für die schnelle Abfrage ohne Order By wird mit Sicherheit ein Index existieren.
Für ein erstes Abschätzen wird dann die Index-Statistik (DSPFD) herangezogen. Hier ist im Wesentlichen die Anzahl der unterschiedlichen Schlüssel der Knoten vermerkt. Ab irgendeinem Prozentsatz wird der Index genommen oder eben nicht.
Kommt nun noch ein Order By dazu (ähnlich auch Group by) entscheidet dann bei fehlenden Indizes der Pessimizer dann auch gerne mal falsch und hält einen Tablescan für besser.

Allerdings muss ich auch dazu sagen, dass per STRSQL da durchaus anders optimiert wird (FIRSTIO) als z.B. bei embedded SQL oder auch ODBC (ALLIO).
Wobei ich die Optimize-Klausel da schon ausprobiert habe aber kein abweichendes Ergebnis zustande bekam.