Allora nella tabella utenti ID è ok che sia
INT (5) UNSIGNED not null AUTO_INCREMENT PRIMARY KEY
Mentre nella tabella messaggi ID sarà
INT (5) UNSIGNED not null

in quanto i valori li metti tu e corrispondono agli id degli utenti e non devono incrementarsi in automatico. Non è neanche una chiave primaria in quanto se un utente scrive più messaggi la chiave non può essere unica.