Something is wrong somewhere because I've setup a category that makes Wiki pages only available to some custom groups, but not the standard "Registered" group and it works just fine (Registered users not in one of the custom groups cannot see Wiki pages under that category).
Check category administration, make sure that the option to ignore category permissions is unchecked. As always, clear your Tiki caches. Are you absolutely sure that you're removing permissions from the Registered user group? Are your other user groups children of the Registered user group? That is to say, they inherit permissions from the Registered user group (I don't think this is necessary but it's how my user groups work).