I like the idea of starting with a master hash that gives the stringification of each complex data type. Making that the basic unit for manipulation, rather than a separate internment step, is interesting.
But your simple elegant code is relying on implicit stringification, and repeated stringification of the same values. This is inefficient if it's a complex data structure, and needs an explicit call in the general code to handle ad-hoc data structures that are not blessed into a class with a stringify operator that's suitable for this purpose.
As for getting a fake "" key you need to toss out, I don't think that's a problem if you make sure that the stringification never returns "" for a valid item in the set.
Ultimately, I think the answer to "how do I find an intersection" isn't to repeat some incantation invented by someone else, but to simply call intersection. The algorithm should be canned in a CPAN module.