I'm not a Mercedes tech so this is just a thought...
I believe that all of the fuel injected engines require a check valve to hold fuel pressure. In my 420SEL it is located at the fuel pump between the pump and the fuel hose. They are only around $20.00 USD.
On cold start my 450SEL starts right up - it's 6 years older. With a bad fuel check valve the 420SEL had to crank for several seconds. (It would not take 10-15 minutes - I was hoping you were exagerating there) The fuel pump even without the check valve should bring the pressure up within 5 to 15 seconds.
It's worth a try - cheap anyway... Good luck!