Acabo de intentar georreferenciar la imagen con QGIS, utilizando sólo 3 puntos, una transformación Helmert y el mapa OpenStreetMap como imagen de referencia.
Llegué a unos 30 km de error de georreferencia, y mis puntos de enlace están casi en línea recta.
Utilizando 7 puntos distribuidos más equitativamente consigo que el error baje a unos 25 km (más en la costa este, véase la imagen).
Utilicé estos puntos de enlace (las coordenadas del mapa están en EPSG:3857):
mapX,mapY,pixelX,pixelY,enable
18817930.309071384370327,-5444407.71369334869086742,509.96686746987938932,-1318.85783132530104922,1
19814517.24758825078606606,-4672001.05644164700061083,1229.98433734939749229,-746.78915662650592822,1
19483979.98175487294793129,-4856145.33167078252881765,980.58493975903604678,-876.42048192771085269,1
19601248.11250143498182297,-4677296.48550668079406023,1073.58132530120474257,-753.83433734939751503,1
18741851.22133468464016914,-5843486.62186039518564939,472.62740963855395648,-1587.98373493975850579,1
19219123.11835713684558868,-5392862.69045551493763924,789.6605421686747377,-1270.95060240963857723,1
19691953.68777665868401527,-4794479.20610703900456429,1142.62409638554208868,-839.08102409638581776,1
(Imagen de fondo (c) Colaboradores de OpenStreetMap imagen de trama de OP (estado/licencia/autor poco claros)
Tal vez pueda mejorar con el uso de más puntos, y también de puntos no urbanos.
Ten en cuenta que el grosor de línea de tu mapa original es de 5 km.
edit: Usando "Thin Plate Spline", nearest neighbor sampling, 12 tie points, llego a esto:
los puntos de empate son
mapX,mapY,pixelX,pixelY,enable
18817930.309071384370327,-5444407.71369334869086742,509.96686746987938932,-1318.85783132530104922,1
19483979.98175487294793129,-4856145.33167078252881765,980.58493975903604678,-876.42048192771085269,1
19601248.11250143498182297,-4677296.48550668079406023,1073.58132530120474257,-753.83433734939751503,1
18741851.22133468464016914,-5843486.62186039518564939,472.62740963855395648,-1587.98373493975850579,1
19219123.11835713684558868,-5392862.69045551493763924,789.6605421686747377,-1270.95060240963857723,1
19691953.68777665868401527,-4794479.20610703900456429,1142.62409638554208868,-839.08102409638581776,1
19800082.9328787624835968,-4760144.32733055297285318,1226.99013554216867306,-812.66159638554211142,1
19876439.60359066352248192,-4535857.28338263556361198,1289.86837349397546859,-650.97469879518098423,1
19259607.5276607871055603,-4083354.3287611361593008,797.41024096385490338,-312.10150602409657949,1
19267123.62052728235721588,-4189262.91006175195798278,803.04638554216808188,-391.71204819277130582,1
19386527.00492910295724869,-4353848.26180875860154629,903.08795180722836449,-516.41174698795202858,1
19257899.3247365839779377,-4944715.65329074021428823,823.47740963855346763,-957.44006024096415786,1
No utilice el punto de la ciudad de Gisborne, parece estar fuera de unos 30 km al oeste.
Los comandos GDAL generados por QGIS son:
gdal_translate -of GTiff -gcp 509.967 1318.86 1.88179e+07 -5.44441e+06 -gcp 980.585 876.42 1.9484e+07 -4.85615e+06 -gcp 1073.58 753.834 1.96012e+07 -4.6773e+06 -gcp 472.627 1587.98 1.87419e+07 -5.84349e+06 -gcp 789.661 1270.95 1.92191e+07 -5.39286e+06 -gcp 1142.62 839.081 1.9692e+07 -4.79448e+06 -gcp 1226.99 812.662 1.98001e+07 -4.76014e+06 -gcp 1289.87 650.975 1.98764e+07 -4.53586e+06 -gcp 797.41 312.102 1.92596e+07 -4.08335e+06 -gcp 803.046 391.712 1.92671e+07 -4.18926e+06 -gcp 903.088 516.412 1.93865e+07 -4.35385e+06 -gcp 823.477 957.44 1.92579e+07 -4.94472e+06 "eCtlN.png" "out_eCtlN.png"
gdalwarp -r near -tps -co COMPRESS=LZW "out_eCtlN.png" "eCtlN_TPS_NN.tif"