I won't give a lot of explanations on the code, as the principles are already known, and I think the code is self-explanatory enough.

Anyway, as you will see, I re-factored the code using a tree-like structure, and separated the code in 2 classes. The main class is PropertyObserver, which creates an observable watching the PropertyChanged event of an instance of an object implementing INotifyPropertyChanged, and update the availability of the action if the PropertyName of the event matches the filter list. The PropertyObserver class has children of the same class, each one observing a property. If the object (implementing INotifyPropertyChanged) a property observer is bound to is changed, the property observer refreshes all its children, to subscribe to the PropertyChanged event on the new instance of the object.

There are no special other things to notice, so here is the full code.

The dependencies attribute class:

public class DependenciesAttribute : Attribute, IContextAware
{
    private readonly IEnumerable<string> dependentProperties;
    private readonly IList<PropertyObserver> observers = new List<PropertyObserver>();
    private ActionExecutionContext context;

    public DependenciesAttribute(params string[] propertyNames)
    {
        dependentProperties = propertyNames ?? new string[] { };
        dependentProperties = dependentProperties.OrderBy(x => x);
    }

    private IEnumerable<string> ViewModelProperties(object target)
    {
        var properties = from property in dependentProperties.Select(propertyName => propertyName.Split('.'))
                            where property.Length == 1
                            select property[0];

        if (properties.Contains("*"))
            return from propInfo in target.GetType().GetProperties()
                    where propInfo.CanRead
                    select propInfo.Name;

        return properties;
    }

    public int Priority { get; set; }

    public void Dispose()
    {
        observers.ForEach(x => x.Dispose());
        context = null;
    }

    public void MakeAwareOf(ActionExecutionContext context)
    {
        this.context = context;
            
        INotifyPropertyChanged inpc = context.Target as INotifyPropertyChanged;

        if (inpc == null)
            return;

        foreach (var viewModelProperty in ViewModelProperties(inpc))
            observers.Add(new PropertyObserver(inpc, viewModelProperty, true, UpdateAvailability));

        var otherProperties = from dependentProperty in dependentProperties.Select(propertyName => propertyName.Split('.'))
                                where dependentProperty.Length > 1
                                select dependentProperty;

        foreach (var args in otherProperties)
        {
            var viewModelProperty = args[0];
            var observer = observers.FirstOrDefault(po => po.PropertyToWatch == viewModelProperty);

            if (observer == null)
                observers.Add(observer = new PropertyObserver(inpc, viewModelProperty, false, UpdateAvailability));

            observer.AddChild(args);
        }
    }

    private void UpdateAvailability(IEvent<PropertyChangedEventArgs> ev)
    {
        Execute.OnUIThread(() => context.Message.UpdateAvailability());
    }
}

and the PropertyObserver:

public class PropertyObserver : IDisposable
{
    private readonly INotifyPropertyChanged parentINPC;
    private readonly string propertyToWatch;
    private readonly Action<IEvent<PropertyChangedEventArgs>> action;
    private readonly IEnumerable<string> childArguments;
    private readonly IDisposable observer;
    private readonly IList<PropertyObserver> children = new List<PropertyObserver>();
        
    public PropertyObserver(INotifyPropertyChanged parentINPC, string propertyToWatch, bool executeAction, Action<IEvent<PropertyChangedEventArgs>> action)
    {
        this.parentINPC = parentINPC;
        this.propertyToWatch = propertyToWatch;
        this.action = action;

        observer = Observable.FromEvent<PropertyChangedEventArgs>(parentINPC, "PropertyChanged")
            .Where(ev => string.IsNullOrEmpty(ev.EventArgs.PropertyName)
                            || propertyToWatch == ev.EventArgs.PropertyName
                            || propertyToWatch == "*")
            .Subscribe(ev =>
                        {
                            if (executeAction)
                                action(ev);

                            RefreshChildren(ev.EventArgs.PropertyName);
                        });
    }

    public PropertyObserver(INotifyPropertyChanged parentINPC, string propertyToWatch, bool executeAction, Action<IEvent<PropertyChangedEventArgs>> action, IEnumerable<string> childArguments)
        : this(parentINPC, propertyToWatch, executeAction, action)
    {
        this.childArguments = childArguments;
    }

    private IEnumerable<IEnumerable<string>> ChildrenArguments
    {
        get { return Enumerable.Repeat(childArguments, 1).Concat(children.SelectMany(x => x.ChildrenArguments)).Where(x => x != null); }
    }

    private void RefreshChildren(string propertyName)
    {
        var childrenArgs = ChildrenArguments.Where(x => x.First() == propertyName).ToArray();

        foreach (var child in children)
            child.Dispose();

        children.Clear();

        foreach (var childArgs in childrenArgs)
            AddChild(childArgs);
    }
        
    public string PropertyToWatch
    {
        get { return propertyToWatch; }
    }

    public void AddChild(IEnumerable<string> arguments)
    {
        var args = arguments.ToArray();

        if (args[0] != propertyToWatch)
            throw new ArgumentException();

        if (args.Length - 2 == 0)
        {
            var childObserver = CreateChildObserver(args, true);
            if (childObserver == null)
                return;

            children.Add(childObserver);
        }
        else
        {
            var childProperty = args[1];
            var child = children.FirstOrDefault(po => po.PropertyToWatch == childProperty);

            if (child == null)
            {
                child = CreateChildObserver(args, false);
                if (child == null)
                    return;

                children.Add(child);
            }

            child.AddChild(arguments.Skip(1));
        }
    }

    private PropertyObserver CreateChildObserver(string[] args, bool executeAction)
    {
        var propertyName = args[0];

        var property = GetProperty(parentINPC, propertyName);

        var inpc = property as INotifyPropertyChanged;

        return inpc == null 
            ? null 
            : new PropertyObserver(inpc, args[1], executeAction, action, args);
    }

    private object GetProperty(object target, string propertyName)
    {
        var propInfo = target.GetType().GetProperty(propertyName);
        if (propInfo == null)
            return null;

        return propInfo.GetValue(target, null);
    }

    public void Dispose()
    {
        observer.Dispose();

        foreach (var child in children)
            child.Dispose();
    }
}

I hope you found this useful.

See you soon!