Ambas opciones que mencionás no son ni polimorfismo ni double dispatch, sino simplemente sobrecarga de métodos. La sobrecarga de métodos es necesaria para el double dispatch pero no suficiente; hace falta visitar al parámetro recibido (de ahí el nombre del patrón Visitor) y luego sobrecargar los métodos.

El problema de diseño que mencionás en tu tercer párrafo es una de las consecuencias conocidas del double dispatch, que puede ser válida si el problema que soluciona es mayor. Recordá que todos los patrones solucionan algún problema de diseño pero generan algún otro. Dependiendo del contexto pueden convenir o no y en cada caso es necesario justificar la decisión.

El mejor ejemplo es el TP2 en donde hay muchas situaciones similares. Te recomiendo si no revisar el ejemplo clásico del Piedra-Papel-Tijera e intentar primero aplicar double dispatch al ejemplo de Pokemon.