Standard Python idiom for creating unique sentinel values is to create an object() just for the job (since if you try to == it will fall back to is). So:

if dictionary.get(key, object()) == value:

gets you the same solution without NaN abuse. And remember that objects are pretty lightweight—they don't even have a __dict__.

Again, vulnerable to stupid classes such as:

>>> class bar:
...   def __cmp__(self, other):
...     return 0

but as fanf says, if you do that, you deserve to lose.

If value can be a bar then I think the whole concept is an intractable problem. (Unless you know about bar and special case it, and given that the original issue was how to do this elegantly, that fails heavily.)