ObservableCollection dependency property does not update when item in collection is deleted

A change within the collection won't trigger the OnSpecialDaysChanged callback, because the value of the dependency property hasn't changed. If you need to react to detect changes with the collection, you need to handle the event CollectionChanged event manually:

private static void OnSpecialDaysChanged(DependencyObject d, DependencyPropertyChangedEventArgs e)
{
  var calendar = d as RadCalendar;

  if (e.OldValue != null)
  {
    var coll = (INotifyCollectionChanged)e.OldValue;
    // Unsubscribe from CollectionChanged on the old collection
    coll.CollectionChanged -= SpecialDays_CollectionChanged;
  }

  if (e.NewValue != null)
  {
    var coll = (ObservableCollection<DateTime>)e.NewValue;
    calendar.DayTemplateSelector = new SpecialDaySelector(coll, GetSpecialDayTemplate(d));
    // Subscribe to CollectionChanged on the new collection
    coll.CollectionChanged += SpecialDays_CollectionChanged;
  }
}

private static void SpecialDays_CollectionChanged(object sender, NotifyCollectionChangedEventArgs e)
{
    // handle CollectionChanged
}

This is just to add to the answer by Thomas. In my code I do interact with the DependencyObject's properties by creating a handler object localy like below:

private static void OnSpecialDaysChanged(DependencyObject d, DependencyPropertyChangedEventArgs e)
{
    var action = new NotifyCollectionChangedEventHandler(
            (o, args) =>
                {
                    var calendar = d as RadCalendar;

                    if (calendar!= null)
                    {
                        // play with calendar's properties/methods
                    }
                });

    if (e.OldValue != null)
    {
       var coll = (INotifyCollectionChanged)e.OldValue;
       // Unsubscribe from CollectionChanged on the old collection
       coll.CollectionChanged -= action;
    }

    if (e.NewValue != null)
    {
       var coll = (ObservableCollection<DateTime>)e.NewValue;
       // Subscribe to CollectionChanged on the new collection
       coll.CollectionChanged += action;
    }
}

Hope this is helpful to someone.

If you have a collection-type dependency property keep the following in mind:

If your property is a reference type, the default value specified in dependency property metadata is not a default value per instance; instead it is a default value that applies to all instances of the type. [...]
To correct this problem, you must reset the collection dependency property value to a unique instance, as part of the class constructor call.

(see MSDN Collection-Type Dependency Properties)

To answer Sam's question (I just ran into the same problem):

Make your CollectionChanged-handler non-static and unsubscribe/re-subscribe on instance-level.

private static void OnSpecialDaysChanged(DependencyObject d, DependencyPropertyChangedEventArgs e)
{
  var calendar = d as RadCalendar;

  if (e.OldValue != null)
  {
    var coll = (INotifyCollectionChanged)e.OldValue;
    // Unsubscribe from CollectionChanged on the old collection of the DP-instance (!)
    coll.CollectionChanged -= calendar.SpecialDays_CollectionChanged;
  }

  if (e.NewValue != null)
  {
    var coll = (ObservableCollection<DateTime>)e.NewValue;
    calendar.DayTemplateSelector = new SpecialDaySelector(coll, GetSpecialDayTemplate(d));
    // Subscribe to CollectionChanged on the new collection of the DP-instance (!)
    coll.CollectionChanged += calendar.SpecialDays_CollectionChanged;
  }
}

private void SpecialDays_CollectionChanged(object sender, NotifyCollectionChangedEventArgs e)
{
    // handle CollectionChanged on instance-level
}