Why won't my WPF bound Visibility property update?

I have a textblock in my XAML where the Visibility is bound to a property in my viewmodel. When the window first loads, the value from the viewmodel determines the visibility correctly (I tried manually overriding the backing store variable value and it works great, hiding the control as I need). However, when I change the property value the visibility doesn't change.

Here's the XAML for the control:

<TextBlock Text="Click the button" Style="{StaticResource Message}" Visibility="{Binding NoResultsMessageVisibility}" />

The "NoResultsMessageVisibility" property that I bind to is this:

    public Visibility NoResultsMessageVisibility
    {
        get { return _noResultsMessageVisibility; }
        set
        {
            _noResultsMessageVisibility = value;
            NotifyPropertyChanged("NoResultsMessageVisibility");
        }
    }

NotifyPropertyChange raises a PropertyChanged event for the provided name using standard INotifyPropertyChanged.

Can anyone spot my mistake?

EDIT

In response to the comments / answer so far.

The program is super simple so there's no parallelism / multithreading used. The DataContext is set only once when the window loads, using:

new MainWindow { DataContext = new MainWindowViewModel() }.ShowDialog();

The binding does seem to work when first loaded. I've noticed as well that a textbox I have bound to a property isn't updating when I change the property. However, the property is definitely updating when I change the textbox as the value is used as the basis for a command that's bound to a button. As the text changes, the button is enabled and disabled correctly and when I click it the value from the property is c开发者_运维百科orrect. Again, if I set a value against the backing store variable, this shows in the textbox when the window first loads.

Don't see anything wrong with this, is it possible that the DataContext gets changed, so the binding breaks? (You only specify the path, so it's relative to the current DataContext)

Solved it. I'm a dozy dork :)

I have copied some code from another class and for some reason I'd added the PropertyChanged event to my viewmodel's interface, rather than implementing INotifyPropertyChanged on the interface. D'Oh!