Great to hear from you so soon, YMsin.
OK, the "little red relay which can be found at the centre of the firewall of your car, just about a feet and a half towards the left of your battery compartment. It looks like a block Chinese Seal with a red square top". Actually I did find something similar in that exact location few days ago, with this part number: 011 545 5028. However, it has a black square top (I know I sound stupid, but perhaps someone painted it black or the batch that it came with had different colored caps).
Next thing I did was to call up 8 different MB parts shops to ask for that part. All of them dont carry it, and I was told that it is just a simple socket/plug, which cost only about US$1.50. Geee....I dont suppose a relay could be this cheap, does it? So I rested my case then thinking that this is just a socket/plug.
But I think they could be wrong. Going by your description, that should be the idle control relay.
I'm gonna make more calls, and thanks to you Ymsin, you've been very helpful.
PS.Just discussed the issue on timing with my mechanic yesterday. He said he could lower the timing if I want, but that'll leave me with less power (which was not something I wanted to compromise on). So I left it at that. Perhaps I'll get the timing checked again later somewhere else.