Ok, Thanks to Dragan and many many tests I actually did figure it out. This is where the problem was:
<ScrollViewer
Grid.Column="2"
HorizontalScrollBarVisibility="Auto"
VerticalScrollBarVisibility="Auto">
<Frame
x:Name="_mainFrame"
Grid.Column="2"
Margin="0"
HorizontalAlignment="Stretch"
VerticalAlignment="Stretch"
NavigationUIVisibility="Visible" />
</ScrollViewer>
The ScrollViewer broke the widths... As soon as I removed that, all works as expected.
Dragan, I would like you to get the credit for this solution - how do I do that?