The problem was in my head. Just because you tell yourself "this is a sandbox" doesn´t mean that your brain stops functioning as usual. Humans are creatures of habit, and all those story-based campaign left certain imprints on my DM-style that were hard to overcome.
DMs like certain parts of their world, and don´t like others. They prefer certain locations and concepts. In a sandbox, you have to watch out for unconsciously acting on those preferances, overriding the players goals. As we say in German: Gefahr erkannt, Gefahr gebannt - a.k.a. if you know about this, you´re halfway there not to have it happen.
EDIT: IMPORTAND - Don´t overlook the awesome adventure "Monument of the ancients" by Brian R. James and Matt James in Dungeon 170. You won´t need the story for a sandbox, but the cool background descriptions and maps will help you a lot. THIS is what should have been in Moonsea.