trata usando Javascript dentro del PHP
Código PHP:
<?php
if(isset($_COOKIE['completo']))
{
// ninguna accion
}
else
{
echo "<script type=\"text/javascript\">
window.open('mensaje.html', 'pop', 'width=300, height=100, top=0, left=0');
</script>";
}
Tú ya le das los parámetros que necesite tu ventanita.
El problema es que existen bloqueadores de popus como Firefox, Windows XP con el Service Pack 2, Google Toolbar u otras herramientas, y no sabemos que tan efectivo puede resultar tu mensaje, te recomendaría solamente mandar un mensaje con letras rojas y grandes en la misma página.
Saludos