Well the article doesn't talk about performance, but at least for the double-maybe in the store example, there is one level of extra indirection in the machine

Well the article doesn't talk about performance, but at least for the double-maybe in the store example, there is one level of extra indirection in the machine code: return pointer to maybe, then return pointer from string from it. If you care about performance, you really need two predicate values to cover this case. You could have (void * )0 for no entry, and (void * )1 for entry exists, but is blank.