Very very niche bug - by default items are listed alphabetically in the Replace action, however it appears that once there are 100k rows (or more), the list defaults to the data source order. A Sort action before the Replace doesn't fix this.
I'm using the Replace function for a Text Classification exercise, the Trim table provides a workaround, but thought I'd flag!