Maybe I finally found how to workaround this and the untold root cause of it. Messages indexing of a large Message application.
Messages exists since the first iOS and so users migrating from different iPhone (as me) may have a huge messages (SMS, iMessage) database. This is probably the culprit as Spotlight tries to index it and end-up in being laggy or broken. Especially, that there is the option to keep SMS messages for ever.
The workaround I found: Disable search indexing for the message app.
Go to Settings > Siri & Search > Messages and then disables all the switch toggles.
The number of people complaining about this bug is so high that it is still incredible that there is no fix for it.