A typical (general) way to speedup evaluation of expressions like this is through "forward differencing" I had a quick look at turned up this, which looks to be the right sort of approach but I can't vouch for its accuracy as I haven't read it properly. Hope that helps (caveat, I haven't read your links completely, either, so this might be nothing new...)
Forward differencing is very fast, but it has some cost to set up, and it can accumulate error as you step along the curve. If you're using double-precision floats, you don't need to worry much about the error issue, but if you're using fixed point or integers, it can be significant.
In my experience, the forward differencing set-up cost is only worth it for more than 2*(N+1) evaluations; so for a (say) cubic curve, if you need less than eight points on the curve you're better off just evaluating the curve directly eight times using the formula in the original post.
Note the formula is actually pretty quick if you expand out the polynomials & collect the terms for frequently used values of N.