I found a temporary solution that works for myself (for the time being, while waiting Apple to hear our loud complains and to restore the loved feature):
On the server (via web-mail access and not on the iPhone):
I created a sub-folder to my Inbox,
named it "Inbox Archive",
moved there all the emails older then a month.
The logic is that the iPhone sync only the content of the Inbox itself.
In the meantime, all my emails, which I do not want to delete, are still there, stored in a sub-folder,
so an eventual search demand in future will simply have to "include sub-folders content".
The above refers to my POP account.
Not sure if sync with IMAP account would work same way (still did not test my gmail)