Speed of looking up .NET Dictionary value by key?

I have a dictionary of 10000 Product/Colour/Size combinations which I have created with something like:

AllRecords = DB.ProductColourSizes _
             .ToDictionary(function(b) String.Format("{0}_{1}_{2}", _
             b.ProductCode, b.ColourCode, b.SizeCode))

So an example key is like "13AI_GRS_M"

I have to sync up my database with the company's ERP every 30 minutes, and for every Colour/Size combo I need to use this dictionary to add, edit or delete records. I wish they supplied ID numbers.

I don't know how Dictionary works internally. How quick is .NET at finding the right value based on such a key? Should I sort the database query, or does .NET have some other way of identifying the key?

Or should I convert it into a List and use a Dictionary to identify the right index? Or another way completely?

I also use Static Dictionaries in this way all over website's application, so learning a better way of doing this would have quite an influence.

Many thanks, Steve