Looking up an entry is O(1) -- just a trivial hashing operation and one or two pointer chases.

So basically what you're saying is that you can make the node do a memory access per 32 bytes sent,  but virtually any network message also does that.  E.g. getblock .

Locators have no reason to be larger than O(log(blocks)), so indeed it's silly that you can send a big one... but I wouldn't expect it to be interesting. Alternatively, you could consider what is the difference between sending 100k at once vs 20 (a totally reasonable number) many times? Only a trivial amount of network overhead and perhaps a couple milliseconds of blocking other peers whos message handling would otherwise be interleaved.  If you benchmark it and find out that its significantly slower per byte sent then other arbitrary messages I'd be interested to hear... but without a benchmark I don't find this interesting enough to check myself.  

There are a billion and one things that are conjecturally slow, but most of them are not actually slow (and more than a few things that seem fast are actually slow).  Anyone can speculate, testing is what is actually valuable.