> Characteristics of the data: the names are relatively short (1-10
> characters usually)

$ ./python -m timeit -s "a = 'hundred'" "'x' in a"
10000000 loops, best of 3: 0.0431 usec per loop
$ ./python -m timeit -s "a = 'hundred'" "a.find('x')"
1000000 loops, best of 3: 0.206 usec per loop
$ ./python -m timeit -s "a = 'hundred'" "a.replace('x', 'y')"
10000000 loops, best of 3: 0.198 usec per loop

Basically, it's simply the overhead of method calls over operator calls. You only see it because the strings are very short, and therefore the cost of finding / replacing is tiny.