La configuración de conexión de MySQL podría tener la culpa aquí. Ejecute este comando MySQL cuando se conecte a la base de datos desde PHP, antes de ejecutar cualquier otro comando SQL:
SET names 'utf8';
Esto debería establecer la codificación de la conexión en UTF-8. Como dices, la página y la base de datos ya están en UTF-8 (eso también debería significar que la página envía Content-Type: text/html; charset=utf-8 ); la conexión en sí puede tener accidentalmente una codificación diferente por defecto :(
