Apparently it's a problem with the order of how bindings are updated when a new DataContext is set. When the ItemsSource-binding gets a new DataContext it notices (in some cases) that the selected item is not present in the new list, which then goes about setting SelectedItem to null and also validates this. Then the SelectedItem-binding gets the same DataContext as ItemsSource, is updated to it's correct value but without any validation to clear out previously failed rules.
The moment I changed the order of the bindings it worked! (in xaml that is)