The most important piece of information is that at this moment I am unable reproduce the issue with the online router. However, I have looked into the git repository for the project and nothing has changed since the time that I encountered the problem (and for sure it was not a data problem either) so I am reporting it here.

Two days ago I played briefly with the online router of the OSRM project and have found a combination of starting and ending point which would make the router choose and absurd path. I tried to simplify the case and the shortest route for which the problem showed was:
http://map.project-osrm.org/X9

The problem was that the router instead of taking the shortest possible way for the default route on a motorway crossing in Brno, missed the exit, followed the motorway for about 20 km, exited the motorway, made a U-turn, entered the motorway again, went back for the 20 km and finally took the exit it should have taken when passing it for the first time. The route went through this way point:
http://map.project-osrm.org/XC
and looked like this:
http://img9.imageshack.us/img9/4548/brnorouterbugoverview.png

It was not a problem with the data because the alternate route went also through Brno and took the exit without any problem. It looked like this:
http://img507.imageshack.us/img507/8798/brnorouterokoverview.png