Is it ever necessary to extend an analysis of Grover's algorithm beyond $k/N = 1/2$? Is it ever necessary to extend an analysis of Grover's algorithm beyond $k/N = 1/2$, where $k$ is the number of "hits" in a total of $N$ possible values for $|\,x\rangle$? 
If we know $k$, and know that it is greater than $1/2$, can't we just redefine hits as misses by modifying the oracle to produce
$$-(-1)^{f(x)}\,|\,x\rangle$$
(note the additional negative sign) and then measure according to whatever strategy for $k<1/2$ produces satisfactory hit probabilities, $p_h$, since we can then say with confidence $p_h$ that one of the unobserved outcomes is a hit?
 A: Consider a state $\def\ket#1{|#1\rangle}\ket{\psi(\alpha)} = \cos(\alpha) \ket{U} + \sin(\alpha)\ket{M}$, where $\ket{U}$ and $\ket{M}$ are respectively the uniform superpositions over the unmarked and marked elements. 
Note that the uniform superposition $\ket{\Psi} \propto \ket{0} + \ket{1} + \cdots + \ket{N-1}$ is such a state, specifically $\ket{\Psi} = \ket{\psi(\theta)}$ such that $$\sin(\theta) = k/N, \qquad\qquad\cos(\theta) = \sqrt{1 - k^2/N^2\,}.$$ Grover's iterate rotates the state within the set of such states, by mapping $\ket{\psi(\alpha)} \mapsto \ket{\psi(\alpha + 2\theta)}$.
Suppose that $N/2 < k < N$, and let $\theta' = \pi/2 - \theta > 0$. Then $2\theta = \pi - 2\theta'$. That is to say, applying Grover's iterate is equivalent to a rotation of $\pi - 2\theta'$; and as the rotation of $\pi$ is equivalent to a global phase (which changes the vector which we use to representing the state, but not the state itself), we may say that the effect is the same as a rotation by $-2\theta'$. The effect is then to rotate the state away from $\ket{M}$, the target state which we would like to sample from. Applying Grover's algorithm when $k > N/2$ is then counterproductive.
What happens when you "relabel" the marked elements as unmarked, and vice-versa? Well, changing the labels you give to them doesn't change what set you end up sampling from; the only place that this makes a difference is in the sign-flip for reflecting about the "unmarked items" axis. But this only differs from reflecting about the "marked items" axis by a global phase of $-1$, which (again) has no effect on the state.
So no matter what you call the set $M$ of items you would like to sample from, if it contains $k > N/2$ items, you're better off not using Grover's algorithm at all, and just doing random sampling.
As a final remark, consider what happens when $k = N/2$: in this case we have $\theta = \pi/4$, and the rotation is by angles of $\pi/2$ — which maps $$\begin{align*}\tfrac{1}{\sqrt 2} \ket{U} + \tfrac{1}{\sqrt 2} \ket{M} \;&\mapsto\; -\tfrac{1}{\sqrt 2} \ket{U} + \tfrac{1}{\sqrt 2} \ket{M} \\&\mapsto\; -\tfrac{1}{\sqrt 2} \ket{U} - \tfrac{1}{\sqrt 2} \ket{M} \\&\mapsto\; \tfrac{1}{\sqrt 2} \ket{U} - \tfrac{1}{\sqrt 2} \ket{M}
\\&\mapsto\; \tfrac{1}{\sqrt 2} \ket{U} + \tfrac{1}{\sqrt 2} \ket{M}\end{align*}$$
cyclically, and to no effect at all. Similarly, if $k < N/2$ but $1/2 - k/N \ll 1$, the amount of time to amplify from $\alpha = \theta$ to $\alpha = \pi/2$ will be about the same as if $k/N \ll 1$, so that it's very counterproductive to use Grover's algorithm rather than just sampling items until one obtains elements of $M$.
For $k/N$ much larger than $1/4$, there's simply no benefit (asymptotic or otherwise) to using Grover's algorithm.
