Mudar a ordem é bom, desde que todos os valores da folha sejam substituídos. Se sua planilha contivesse 11, o que não seria substituído, a alteração da ordem ainda a substituirá por hello1.
Para usar a célula inteira da correspondência, especifique
,LookAt:=xlWhole
como outro parâmetro para o método Replace. Substituir é um método válido em um intervalo, portanto, o loop For não é necessário. Você pode especificar
Range("A1:A1000").Replace What:="12", Replacement:="goodbye", LookAt:=xlWhole
Range("A1:A1000").Replace What:="4", Replacement:="cat", LookAt:=xlWhole