El topónimo Madina

 Madina es una casa de Hernani. Hay un topónimo derivado, el palacio Madinabeitia de Oñati. En este último pueblo debió de tener origen este topónimo, teniendo en cuenta los testimonios de la segunda mitad del siglo XX del libro de Iñaki Linazasoro Caseríos de Guipúzcoa, del barrio Araotz de Oñati:

MADINA ALDEKOA (prop.)
MADINA-AZKOITIKO AUNDIA (MADINAZKOITI) (desh.)
MADINA-AZKOITIKO TXIKIA (MADINAZKOITITXO) (des.)
MADINA AZPIKO AUNDIA (desh.)
MADINA AZPIKO TXIKIA (pr.)
MADINA BEITI ((prop.)
MADINABEITI AZPIKOA (prop.)
MADINA-GARAIKO AUNDIA (prop.)
MADINA-GARAIKO TXIKIA (col.)

Los testimonios más antiguos son del siglo XVI, en la web Dokuklik, donde aparecen los registros sacramentales de la comunidad autónoma vasca. En estos documentos se muestran los registros de bautismo, matrimonio y defunción y los testimonios del apellido Madina aparecen bastante pronto, ya que desde el año 1539 son bastante abundantes:

Se puede ver que el topónimo es muy parecido a la palabra Medina, que aparece en la toponimia española, ya que en árabe es 'ciudad'. Algunos nombres conocidos son Medina Azahara (Córdoba), Medina Sidonia (Cádiz), Medina de Pomar (Burgos) y Medinaceli (Soria). Algunos no están lejos del territorio vasco, como el de Burgos o el de Soria. Pero, a pesar del parecido, la explicación para Madina será diferente. En el libro Apellidos vascos de Koldo Mitxelena se habla de el parecido pero no se ve vínculo: 

La etimología vendrá de otro sitio, aunque también habrá una palabra en árabe. Para llegar a su explicación es necesario mostrar otro topónimo, Las Badinas, de Tafalla. En la base de datos EODA de Euskaltzaindia se recoge una mención de la colección Nafarroako Toponimia eta Mapagintza, XL, 114:

[...]
OBS.- Paraje al S.de la ciudad; depresión húmeda, con manantiales y juncales, cruzada por el "Barranco de las Badinas", afluente del Lavaco. Según J.M.Iribarren se denomina badina: 1) Charca o balsa formada en los caminos. 2) Embalse. 3) Remanso grande de agua. 4) Charco de agua cenagosa. 5) Cantidad excesiva de líquido extendido sobre una superficie. Proviene del árabe batén.
[...]

Esa palabra, badina, también se usó en euskera:

badina.
Lago.
Desenbarkatrik badinaren berze aldeko erribran. Samper Mt 8, 28 (Hual lago, Ur itsaso).

Por tanto, hubo un cambio, la oclusiva del inicio cambió, quizás por influencia de la nasal posterior: b-n > m-n. Esa asimilación es bastante conocida en euskera, por ejemplo, la palabra mihi 'lengua', tendría origen en un más antiguo *bini. Es cierto también que a veces ocurre un cambio b- > m- sin una nasal cercana. Así, en la base del topónimo Martolobaso está en antropónimo Martolo, una variante de Bartolo.
Por otra parte, en la explicación del topónimo Las Badinas aparece la palabra batén que también ha pasado al euskera como patin:

patin.
1. (V-ger-ple-arr-oroz-m-gip; Zam Voc ). Ref.: A; EAEL 69.
"Aljibe, cisterna" A. "Pozo" Zam Voc.
[...]

Por tanto, de la palabra árabe batén hay dos palabras en euskera, badina y patin, ambas seguramente tomadas del romance.