I found out why - the HttpMethodConstraint does not check the X-HTTP-Method-Override field and so, for example, in that article, the HttpMethodConstraint was set to only allow "PUT", but of couurse "POST" was being returned by HttpContext, so it failed.
I wrote my own RouteConstraint and have posted it here so others may learn from my trouble.
    public class HttpVerbConstraint : IRouteConstraint {
    public HttpVerbConstraint(params string[] allowedMethods) {
        if (allowedMethods == null) {
            throw new ArgumentNullException("allowedMethods");
        }
        this.AllowedMethods = allowedMethods.ToList<string>().AsReadOnly();
    }
    protected virtual bool Match(HttpContextBase httpContext, Route route, string parameterName, RouteValueDictionary values, RouteDirection routeDirection) {
        if (httpContext == null) {
            throw new ArgumentNullException("httpContext");
        }
        if (route == null) {
            throw new ArgumentNullException("route");
        }
        if (parameterName == null) {
            throw new ArgumentNullException("parameterName");
        }
        if (values == null) {
            throw new ArgumentNullException("values");
        }
        string method = httpContext.Request["X-HTTP-Method-Override"] ?? httpContext.Request.HttpMethod;
        switch (routeDirection) {
            case RouteDirection.IncomingRequest:
                return AllowedMethods.Any(v =>
                v.Equals(method, StringComparison.OrdinalIgnoreCase));
            case RouteDirection.UrlGeneration:
                string verb = "GET";
                if (values.ContainsKey(parameterName))
                    verb = values[parameterName].ToString();
                return AllowedMethods.Any(v =>
                    v.Equals(verb, StringComparison.OrdinalIgnoreCase));
        }
        return true;
    }
    bool IRouteConstraint.Match(HttpContextBase httpContext, Route route, string parameterName, RouteValueDictionary values, RouteDirection routeDirection) {
        return this.Match(httpContext, route, parameterName, values, routeDirection);
    }
    public ICollection<string> AllowedMethods { get; set; }
}