FWIW, sets and dicts convert back and forth very efficiently (the hash values are reused and the collection is presized with just a single memory allocation).  Also, the sets and dicts have shared pointers to the underlying data (which is often much bigger than the containers that refers to the data).

Also, the use case of having very large dicts with repeated intersection operations isn't common enough to warrant any significant code expansion (your solution two).   

I don't understand your "solution one".  PySet_New(self) does copy references to the keys from the dict to a set and the intersection_update() does perform operations on that set.

Lastly, since there was no clear example given, there isn't an opportunity to look at it to see if the code would have been better designed to simply use sets for the set operations and keep the dict around to the key to value transformations (in other words, the current toolset may already afford some way to accomplish the goal).