Buenas.
Se podría hacer accesible y responsive pero a base de más trabajo. Para que fuera accesible habría que incluir como primera opción una lista con el menú en el código html, que sería la que se mostraría en el caso de que no estuviera disponible la imagen o estuviera desactivado javascript, y esa lista se sustituiría por el mapa de imagen mediante javascript si la carga de la imagen se realiza con éxito. Y responsive puede ser puesto que es una imagen y se puede escalar en función de las reglas de los media query. Las coordenadas deben ser relativas al tamaño de la imagen.
Aunque como ya han dicho debe ser un caso complejo que justifique el tener que invertir más trabajo, como por ejemplo
este menú de globos