La siguiente es la forma mas optima que se validó con el plan de ejecución en Oracle:
SELECT COUNT(0)
FROM ESQUEMA.TABLA
WHERE CAMPO_FECHA >= TO_DATE('01.05.2016:00:00:00','DD.MM.YYYY:HH24:MI:SS')
AND CAMPO_FECHA <= TO_DATE('31.05.2016:23:59:59','DD.MM.YYYY:HH24:MI:SS')
