Issues with {RelativeSource PreviousData} when removing collection elements

I'm using the following (simplified) code to display an element in all the items in an ItemsControl except the first:

<TheElement Visibility="{Binding RelativeSource={RelativeSource PreviousData},
                                 Converter={StaticResource NullToVisibility}}/>

NullToVisibility is a simple converter that returns Visibility.Hidden if the source is null, Visibility.Visible otherwise.

Now, this works fine when binding the view initially, or adding elements to the list (an ObservableCollection), but the element is not made invisible on the second element when removing the first.

Any ideas on how to fix this?