Este problema se conoce como Lectura fantasma :
Prueba
BEGIN;
SET TRANSACTION ISOLATION LEVEL SERIALIZABLE;
INSERT INTO mytable (myvalue, mykey) SELECT 'randomvalue', 1 WHERE
(SELECT COUNT(*) FROM mytable WHERE mykey = 1) < 5;
END;
El nivel de aislamiento de transacciones garantizará que las transacciones solo inserten valores si el recuento es inferior a 5.