What happens if someone has a pubkey in a categorized list kind 30000 but it doesn't appear in his/her contact list kind 3?
Which clients support these new kinds besides Gossip? 

 You can do that. Gossip manages to get relays and find events for the intersection of all your lists, not just your following list.