UUID index unused

I am assuming I am crazy and missing something completely obvious but I cannot get postgres (9.3.5) to use an index on a UUID, ever.

The main table has a natural composite key (2 uuids and a timestamp) with which it always uses the timestamp as the index condition and filters on the UUIDs. This occurs when when we do a query for a specific item comparing all 3 key columns with equality. Other tables that have a single UUID column index also fail to ever utilize any available indices; querying for a specific UUID always results in a table scan for them.

Switching the UUID columns to text immediately solves the issues and index usage is as expected in all cases.

After hours of fiddling I figured it was time to ask. Any ideas?

P.S. Before it’s suggested… we have millions of independent devices generating the ids which drives our use of UUIDs. Any thoughts of replacing them only result in us building something that’s basically a UUID to replace it.