How is Grover's Algorithm useful? I am at a loss when it comes to understanding how Grover's Algorithm gives any useful information. Suppose we have a 4-qubit states (|0⟩ to |15⟩), and we are searching for the state |3⟩. The oracle would thus be 
O=I−2|3⟩⟨3|

And then, at the end, after all the amplitude amplification steps, we would get the state |3⟩ with a high probability, but does this give any new information, since we already used |3⟩ inside the oracle?

I know I am missing out something crucial, but I absolutely cannot put my finger on it.

Please help. Thank you.
The thing you're missing is that you aren't search for $|3\rangle$, you're searching for "the input that makes $f$ return true" where $f$ is some function.

For example, maybe $f$ is a discrete logarithm checker like $x \rightarrow 2^x \equiv^? 432821 \pmod{7438927891}$. Or $f$ could interpret its input as a claimed proof of the Riemann hypothesis, and check if that proof is correct. Anything you can imagine checking, $f$ could be that.

So Grover's algorithm is very very widely applicable. But unfortunately it also only gives a quadratic advantage, so "applicable" often doesn't translate into "useful". For example, the space of (reasonably sized) possible Riemann-hypothesis proofs is so huge that it laughs at square roots.