The following Treasure Map islands have healers all the time (* also has shrine):
Bald
Temple (in a guard zone, no less)
Valor*
Amoeba
Fire*
North Jhelom
Skull
Serpents Hold
Buccaneer's Den (town healer)
No Healers at all:
Ocarina
Blanche
Horseshoe
Dragon
Iver's rounding
Random spawn Healers (rare); probably due to being within mainland spawn zones.
Eiffel (also can have gypies or brigands)
Dot (some Dev had a sick sense of humor)