Problema con clave ajena

[Lentorro]

Yo quiero que no sea posible crear un registro en la tabla contactoCliente a menos que Fk_idCliente ya exista en la tabla Clientes.

Eso es lo que no funciona. Ambas tablas están vacías. En principio yo no debería ser capaz de crear un registro en la tabla contactoClientes a menos que rellene el campo fk_idCliente con un valor ya existente en el campo idCliente de la tabla Clientes, estoy equivocado? Pues ahí está el error. Incluso estando ambas tablas completamente vacías... puedo crear un registro en la tabla contactoCliente que tenga como fk_idCliente un valor que no corresponde a ningún registro de la tabla Clientes (la misma no tiene ninguno todavía).

Creo esta segunda tabla, contactoClientes, teniendo Clientes sin registro alguno. Estoy usando phpmyadmin. No ves ningún otro posible error? Gracias.

EDITO:

Tenías razón, no entendí en un principio lo de MyISAM, porque como es algo de lo que yo ni siquiera había oído hablar, pensé que no podía tener nada que ver con mi problema. Me posicioné en mi tabla contactoClientes y como motor de almacenamiento tengo MyISAM. Supongo que me viene así por defecto... He estado leyendo y al parecer tengo que cambiarlo y elegir innoDB. Lamentablemente entre las opciones que me aparecen como motor de almacenamiento no hay ningún innoDB. Memory, blackhole, archive, federated... pero ningún innoDB. Alguna idea de cuál debería elegir? Gracias.