This bug has been with Trados Studio since forever but finally I got around to reporting it.

The problem is that after popping up the Find and Replace dialog (above) with Ctrl+H and typing "Find what" string and then "Replace with" string the "Replace All" button does absolutely nothing when you click it for the first time. In order to replace all strings, you need to first click "Find Next" so that the very first string is found and only then you can click Replace All and then it works properly.

This behaviour is inconsistent with all other Windows applications. It would be great if someone could have a look at this at their earliest convenience.