Ok, *somehow* the Sent mail listing issue has fixed itself. I didn't do anything since last looking at the folder, except finish trying to fix my 'Older' folder. After a long while, my Mac OS client finished indexing everything itself and I finally checked the iPhone again. Maybe 30 minutes had passed. Sent mail now shows the recipient's name as it should. Phew.

But my mail moving trick has failed to fix the order of the messages in the Older folder... I'll revisit that again later though.