Localicé el error que tenía...
Yo tengo esto configurado en el select:
Código HTML:
<select name="estado" id="estado" class="input-type-d" required >
<?php include("reglas/estados.php"); ?>
</select> y en estados.php
Código HTML:
<option value="<?php if(isset($row_20)){ echo $row_20; } else { echo '0'; } ?>"><?php if(isset($row_20)){ echo $row_20; } else { echo 'Estado *'; } ?></option>
<option value="Aguascalientes" >Aguascalientes</option>
<option value="Baja California Sur" >Baja California Sur</option>
<option value="Baja California" >Baja California</option>
<option value="Campeche " >Campeche </option>
<option value="Coahuila" >Coahuila</option>
<option value="Colima" >Colima</option>
<option value="Chiapas" >Chiapas</option>
<option value="Chihuahua" >Chihuahua</option>
<option value="Distrito Federal" >Distrito Federal</option>
<option value="Durango" >Durango</option>
<option value="Guanajuato" >Guanajuato</option>
<option value="Guerrero" >Guerrero</option>
<option value="Hidalgo" >Hidalgo</option>
<option value="Jalisco" >Jalisco</option>
<option value="Estado de México" >Estado de México</option>
<option value="Michoacán" >Michoacán</option>
<option value="Morelos" >Morelos</option>
<option value="Nayarit" >Nayarit</option>
<option value="Nuevo León" >Nuevo León</option>
<option value="Oaxaca" >Oaxaca</option>
<option value="Puebla" >Puebla</option>
<option value="Querétaro" >Querétaro</option>
<option value="Quintana Roo" >Quintana Roo</option>
<option value="San Luis Potosí" >San Luis Potosí</option>
<option value="Sinaloa" >Sinaloa</option>
<option value="Sonora" >Sonora</option>
<option value="Tabasco" >Tabasco</option>
<option value="Tamaulipas" >Tamaulipas</option>
<option value="Tlaxcala" >Tlaxcala</option>
<option value="Veracruz" >Veracruz</option>
<option value="Yucatán" >Yucatán</option>
<option value="Zacatecas" >Zacatecas</option> entonces, cuando no selecciono nada el valor es "0", lo que significaba "no vacío", por ello no aparecía el mensaje :/
Era un error que venía arrastrando desde hace mucho y no lo había localizado.
Gracias por cierto PHPeros por tu comentario!! ^^