I don't think any lookup table is provided (the wire order of entries is undefined). They are not lookup maps, they are syntactic sugar for repeated key/value pairs.
The "lookup table" is constructed at parse time. Yes, the items are just key/values on the wire, but when parsed (in C++, at least) they are placed in a google::protobuf::Map, which is hashtable-based. I guess it could differ across languages -- some might not have any specific support for maps yet.
(Proto2 definitely didn't have any built-in notion of maps when I was working on it. I thought maps were added as a proto3 feature...)