Tout d'abord, il y a un certain nombre d'erreurs dans votre code qui le rendent un peu lourd à tester. Deuxièmement, assurez-vous d'utiliser le même jeu de caractères dans les deux tables, j'ai changé message_map en utf8 :
DROP TABLE message_map;
CREATE TABLE message_map (
message_from varchar(15) NOT NULL,
message_id varchar(15) NOT NULL,
message_to varchar(15) NOT NULL,
message_status bit(1) DEFAULT NULL
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
ALTER TABLE message_map
ADD PRIMARY KEY (message_from,message_id,message_to),
ADD KEY FK_ij6tystusydqijqp8lgoigo1c (message_id);
ALTER TABLE message_map
ADD CONSTRAINT FK_MSG_MAP_USER
FOREIGN KEY (message_from)
REFERENCES user (USER_ID)
ON DELETE CASCADE
ON UPDATE CASCADE,
ADD CONSTRAINT FK_MSG_MAP_USER_TO
FOREIGN KEY (message_to)
REFERENCES user (USER_ID)
ON DELETE CASCADE
ON UPDATE CASCADE;
J'ai supprimé la démo de la définition de clé étrangère.