Here is the code of the converter:

public class EmptyCollectionToVisibilityConverter : IValueConverter

{

public object Convert(object value, Type targetType, object parameter, CultureInfo culture)

{

// ReSharper disable once PossibleNullReferenceException

var valueAsEnumerable = value as IEnumerable;

    var hasElements = valueAsEnumerable?.GetEnumerator().MoveNext() ?? false;
    // ReSharper disable once CanExtractXamlLocalizableStringCSharp
    if (parameter as string == "Reverse")
    {
        hasElements = !hasElements;
    }

    return hasElements ? Visibility.Visible : Visibility.Collapsed;
}

public object ConvertBack(object value, Type targetType, object parameter, CultureInfo culture)
{
    throw new NotImplementedException();
}
}

I've checked with WPF and the behavior seems correct.
If the collection changes (items added or removed) but the property itself didn't change (the collection is the same), the binding is not evaluated and the converter is not called.

You probably should use collection Count as the trigger of property change:
<Grid Visibility="{Binding AccessibleVehicles.Count, Converter={StaticResource CountToVisibilityConverter}}">

And use a converter that checks the value of the Count to determine the visibility.

Thank you for investigating! The advice with binding to Count is a golden one :-) I never thought about this!
I'm surprised it was fine before so I assumed it's a bug. Good to know that now it works as intended.
You can close this issue.

You're welcome.