¿La consulta más rápida para verificar la existencia de una fila en Oracle?

Usar COUNT(*) está bien si también usa rownum=1:

declare
   l_cnt integer;
begin
   select count(*)
   into   l_cnt
   from   x
   where  x.col_a = value_a 
   and    x.col_b = value_b
   and    rownum = 1;
end;

Esto siempre devolverá una fila, por lo que no es necesario manejar ninguna excepción NO_DATA_FOUND. El valor de l_cnt será 0 (sin filas) o 1 (existe al menos 1 fila).