> we were only really accessing it by unique keys which seems to remain fast no matter how large the table is.

Even a naive B-tree index has a logarithmic curve, which means that the time to find a record asymptotically flattens out as the number of records increases.