One mystery is solved. From the mouth of akupenguin himself (the author of x264 (mostly)):
So, whereas Zero1's chart about profiles and levels above seems to be true, it seems like there are "certain restrictions" to where and how p4x4 blocks can be used which x264 does NOT check for. That's why megui doesn't let you set the level to 4.1 AND set p4x4 macroblock searching on at the same time. It's more about the specific workings of x264 than the standard itself.
Which is crappy news, since all my previous encodes used that feature
. Well, we'll just need to see if this is more a precaution about extreme circumstances or one which is not really the case. More info is needed.