Quantum algorithm for checking if element exists

I am currently having hard times while facing an interesting idea, which could speed up many present quantum algorithms, but I am not sure whether my thought is not misleading, or more precisely, impossible to realize:

Would it be practicable to check in less than $\sqrt{N}$ time whether there is an element which, if evaluated by an oracle, equals some predefined value? I do not need its position as in case of Grover algorithm. Analogous to Deutsch-Josza algorithm, my first thought was to use the Hadamard gate, which would turn the superposition into a messy state in case there is an element with flipped phase (i.e. marked), otherwise put the register into its starting state.

However, after implementing this in QCL, I found out that this method does not seem to be sustainable as the probability of measuring the same state in both cases continuously increases, so the measured value cannot be regarded meaningful. Thus, the Walsh-Hadamard interference transformation is not about to be a solution to this problem, neither QFT is; it makes me ask you: Do you think there is any way to interfere the qubits so one could get considerable results or am I quite a bit mistaken?

If it were possible to identify whether a particular element existed in a list in $O(N^{\alpha})$ time, you could search for that element in $O(N^{\alpha}\log N)$ time. The method is simple. You perform a binary search, checking at each stage whether the element in present in half the list, and this eventually leads you to the element you want.
Since the fastest a quantum search algorithm can run is $O(\sqrt{N})$, there is no algorithm of the type you want that has $\alpha<1/2$.