I've found 64bit unsigned ints are more than enough for any GUID I've had. I tend to use them as bit fields as well to help identify type and which machine they come from, so I could imagine I could get away with 32 bits in a simpler game. The nice thing is that the comparison is simply an integer comparison, which is really fast.
As for quick look-up, you need to think about how many objects you have total. If you have less than 100 objects, a simple array of objects may actually be faster than using std::map (which if I recall, is a red-black tree data structure). However, if you have many objects (10000-1000000) you may need to test which is better, a std::map or some kind of hash table.