REGEXP e LIKE estão acostumados a casos totalmente diferentes.

LIKE é usado para adicionar curingas a uma string enquanto REGEXP é usado para corresponder um atributo com Expressões Regulares.

No seu caso, um firstname é mais provável que seja correspondido usando LIKE do que REGEXP e, portanto, será mais otimizado.