Thanks everyone who replied to me. I really appreciate it.

I apologize for cross-posting, but I haven't gotten any reply to this post in a few weeks, that's why I decided to open a new threat, to get some attention.

I need to say that I do know about ECU being reset on disconnect of battery, and I'm familiar with various driving cycles. What I haven't mentioned before is that, before doing any repairs I have driven more than 1200 miles since the previous battery disconnect. This is my "weekend" car, so I don't have a routine path. Over several months and more than 1200 miles I'm sure the car have experienced all kinds of driving, and when the car did not passed smog check after 1200 - that's when I realized that there's something wrong with it. After that I have replaced the EGR Valve and the battery. The shop also replaced the spark plugs as a part of regular maintenance and head gaskets to eliminate some leaks. They did some sort of reset, since immediately after replacing the spark plugs I had ABS and BAS and Spolier going up notification. Some sort of reset from their Mercedes tools have cleared everything and only then I drove more than 600 miles using various types of driving.

And now I'm to the square 1, where I was before any repairs - EGR Not Ready.

The problem still exists. Any other help/advice is greatly appreciated.