Buscar número de teléfono desde MYSQL DB

Necesitas un [() -]* entre cada carácter de entrada:

SELECT * FROM `mytable`
WHERE `phone` REGEXP '3[() -]*5'

Esto permite que exista puntuación dentro de su "cadena" de dígitos, pero nada más.