Indeed, a quick test confirms that viewitems() answers queries of this type quickly as I'd expected. I just did this:

>>> d = dict([(i,i*i) for i in range(1000000)])
>>> (5,47) in d.viewitems()
False
>>> (5,47) in d.items()
False

and there was a delay of a second or so when constructing the dictionary in the first place, and when testing via items(), but testing via viewitems() was instant.