If the collection size is small you could go with the solution provided by rich.okelly. However, a large collection means that the generation of the dictionary may be noticeably slower than just searching the keys collection.
Also, if your usage scenario is searching for keys in different points in time, where the NameValueCollection may have been modified, generating the dictionary each time may, again, be slower than just searching the keys collection.