Hello, Jan!
What network dataset are you using? Is your data small enough to zip up and post here? If so, please post it along with a screen shot or MXD that has where your start and destination stops are located.
Otherwise, what type of connectivity policy are you using (any vertex or end point)? Also, you mention that there are no "other restrictions". Just to clarify, this means you have no turn restrictions, oneway restrictions, or anything like that? Do you have hierarchy enabled? If so (or if not), try the other setting and see if you get different results.
To do a little debugging, you could try to use the Network Identify tool (on the Network Analyst toolbar), to step along the route and make sure that the network has the connectivity you expect build into it for that area.
All of that is a good start. We'll work it out until we figure out what went wrong.
Regards,
Patrick