初投稿です。
私も先日この問題にぶつかりまして、
環境はほぼ同じで、お名前.comの共用サーバーSDにeccube-2.12.2をインストールしました際に発生致しました。

もちろん弊社の環境やさくらのレンサバではソートが動作する事を確認しました。

解決方法としましては、
SC_PRODUCT.php、findProductIdsOrderの
$objQuery->setGroupBy('alldtl.product_id');
をコメントアウトするとソート出来るようになります。

原因はお名前.comの共用サーバーSDではphpMyAdminから、
select alldtl.product_id from dtb_products AS alldtl GROUP BY alldtl.product_id ORDER BY alldtl.product_id DESC
のクエリを実行してみるとソートがされないで検索結果が返される事がわかりまして、検証していくと、GROUP BY している構文にORDER BYしているとソートされないようです。
ですので、価格順または、新着順などをクリックしても通常通り
ORDER BY 句が入ったクエリが実行されるが結果としてソートされた結果が返ってきていないのでエラーなども発生せず原因が解りづらい状態となっておりました。

当対応で他の機能への影響があるのかまでは解らないですが、構文をみるかぎりは、
意味のないGROUP BYという感じでしたので、上記のとおり
SC_PRODUCT_EX.phpでfindProductIdsOrder関数をオーバーライドし、$objQuery->setGroupBy('alldtl.product_id');をコメントアウトすることで対応することが出来ましたので報告させていただきます。