Oracle is not using a unique index for a long key
I found the solution! It is so beautiful and I actually learned a LOT about Oracle.

In one word: histograms.

I started reading a lot about how Oracle's CBO works and I stumbled upon histograms. I didn't fully understand so I took a look at the USER_HISTOGRAMS table, and voilá. There were several rows for the sick table, and practically nothing for the cloned table. For the sick table, there was one row for each of the 8 different identifier-starting-parts. And this is the key: they were cut off at 32 characters, before the @ sign. As I said, the first part of keys is highly repetitive, they become different after the @ sign.

It seems that histograms can be more powerful than the simple fact that a unique index always has a cardinality of 0 or 1 for a given value. When I was querying for 2+ rows, Oracle looked at the histogram, it thought that there could be tens of thousands of values for that identifier-starting-part, and it threw the CBO off course.

I deleted the histograms for that column in the old table and the problem went away!

More reading: https://blogs.oracle.com/optimizer/entry/how_do_i_drop_an_existing_histogram_on_a_column_and_stop_the_auto_stats_gathering_job_from_creating