Use reflection to check for class methods with a custom attribute
It's true that reflection is fairly slow, but for one-time operations the performance isn't usually a deal-breaker. 

This method runs once-per-type, "some time before the view model is instantiated"

// optional type alias for clarity in this post
using MethodMap = System.Collections.Generic.Dictionary&lt;System.String, System.Collections.Generic.List&lt;System.Reflection.MethodInfo&gt;&gt;;

public class ViewModelBase : ... 
{
    protected readonly MethodMap ExecuteOnPropertyChangedMap;

    const BindingFlags Flags = BindingFlags.Instance | BindingFlags.Static | BindingFlags.Public | BindingFlags.NonPublic | BindingFlags.FlattenHierarchy;
    protected static MethodMap GetMethodMap&lt;T&gt;() where T : ViewModelBase
    {
        // slight variation on your code here
        var t = typeof(T);
        var map = new MethodMap();
        // This is up to personal preference, but I recommend using 'var' and a constant for Flags to make your code as human readable as possible
        foreach (var method in t.GetMethods(Flags))
        {
            foreach (var execAttribute in method.GetCustomAttributes(typeof(ExecuteOnPropertyChangedAttribute), true))
            {
                if (execAttribute == null) continue;            
                foreach (string propertyName in execAttribute.PropertyNames)
                {
                    if (!map.ContainsKey(propertyName))
                        map.Add(propertyName, new List&lt;MethodInfo&gt;());        
                    map[propertyName].Add(method);
                }
            }
        }
        return map;
    }    

    // ...

    protected ViewModelBase(MethodMap map)
    {
        ExecuteOnPropertyChangedMap = map;
    }
}


Then in each of your view model types, you could add

public class MyViewModel : ViewModelBase
{
    private static readonly MethodMap map = GetMethodMap&lt;MyViewModel&gt;();

    public MyViewModel : ViewModelBase(map)
    {
        // ...   
    }
}


You can put the logic for reflection and building your map in your base class - but your base class doesn't know about its sub types. So each of your sub types is responsible for passing info about itself up to the base class to provide it with an instance-level reference to the sub types map. 

By setting a private static readonly in the sub type we ask C# to 'calculate this some time before we need it but we don't care exactly when',
as opposed to putting it in your constructor. If you put the call to the reflection code in your constructor it happens every time you construct the object (like you pointed out). With this it only happens once, 'some time' before you instantiate the first MyViewModel. In practice, the field will usually be set right before the first MyViewModel constructor is called.