Ok I managed to hard reset it.

The instructions are correct:;
- remove the battery
- replace the battery
- press call + end call + soft reset button (at the same time) (the phone is still off at this moment).

The trouble I had so far is that while pressing the call + end call button, somehow the middle button is also depressed. As a result nothing happens.

So to make sure the center button is not pressed, the trick is to spread your fingers further apart. And test it by pressing the center button. If you can press it down while holding on to the two buttons it means that you're fine. Otherwise it means your fingers are not far apart enough.

Good luck to those who need to do hard reset. I spent a whole day figuring this out.