Uno de los problemas de dibujar líneas directamente sobre el Canvas es el que tú comentas.
Antes de que continues adelante te voy a sugerir que revises el componente
SimpleGraph que puedes encontrar en
DelphiArea. Yo lo he utilizadoy es muy bueno (gratuíto y con fuentes).
No es que quiera cambiarte los planes, pero está justo pensado para cosas como las que tú estás haciendo. Échale un vistazo a la demo a ver si te puede servir.
Si aun así continuas con tu código, creo que la única forma de resolver tu problema es ir redibujando el fondo (en tu caso el mapa) cada vez que borras la línea. Será lento (y seguramente te aparezca un parpadeo), pero con el código que está utilizando creo que no hay otra opción.
Tal vez la alternativa es que las líneas que dibujes sean objetos propios en sí, por ejemplo piensa en TShapes (pero que dibujen líneas).