It seems to me that the diagonalisation arguments that can be used are only slightly different from a standard one, e.g. such as can be found in these lecture notes about the Baker–Gill–Solovay Theorem (i.e., that there are oracles $A$ for which $\mathsf P^A = \mathsf{NP}^A$ and also oracles $A$ for which $\mathsf P^A \ne \mathsf{NP}^A$). Basically, you have to describe how to 'engineer' an adversarial input a little differently.
Here's how we might use this approach to prove the existence of an oracle $A$ for which $\mathsf{NP}^A \not\subseteq \mathsf{BQP}^A$. For any oracle $A$, define a language
$$ L_A = \Bigl\{ 1^n \;\Big\vert\; \exists z \in \{0,1\}^n : A(z,0) = (z,1)\Bigr\} . $$
It is clear that $L_A \in \mathsf{NP}^A$ for the simple reason that a nondeterministic Turing machine can examine whether the input is of the form $1^n$ for some $n$, and then guess a string $z \in \{0,1\}^n$ for which $A(z,0) = (z,1)$ if such $z$ exists.
The goal is to show that $L_A$ cannot be decided in polynomial time, with bounded error, by a uniform unitary circuit family, using the $O(2^{n/2})$ lower bound on the search problem.
Let $c,N > 0$ be such that the search problem on oracles with $n$-bit inputs requires at least $c 2^{n/2}$ oracle queries to decide correctly (with probability at least 2/3), for all $n > N$.
Let $\mathbf C^{(1)}\!$, $\mathbf C^{(2)}\!$, $\ldots$ be an enumeration of all unitary oracle circuit families $\mathbf C^{(k)} \!= \{ C^{(k)}_n \}_{n \geqslant 0 }$, such that the gate-sequence of the circuit $C^{(k)}_n\!$ acting on $n$-bit inputs can be produced in time strictly less than $c 2^{n/2}$. (This time bound relates to the 'uniformity' condition, where we will be interested in circuits can be computed by a deterministic Turing machine in polynomial time — a stronger condition than we impose here. The enumeration of these circuit families could be done, for instance, by representing them indirectly by the deterministic Turing machines $\mathbf T^{(k)}$ which produce their gate sequences, and enumerating those.) We enumerate the circuit families so that each circuit family occurs infinitely often in the enumeration.
From the run-time bounds on the description of the gate sequence, it follows in particular that $C^{(k)}_n$ has fewer than $c 2^{n/2}$ gates for all $k$, and in particular makes fewer than $c 2^{n/2}$ queries to the oracle.
For any $n$, consider the circuit $C^{(n)}_n\!$. From the lower bound on the search problem, we know that for $n > N$ there are possible values of the oracle function $f: \{0,1\}^n \to \{0,1\}$ evaluated by the oracle, such that with probability 2/3, the output produced by $C^{(n)}_n\!$ on input $1^n$ is not the correct answer to whether $\exists z \!\in\! \{0,1\}^n\!:\! f(z) \!=\! 1$.
For each $n > N$, select such a function $f_n$ for which $C^{(n)}_n$ "fails" in this way.
Let $A$ be an oracle which, on inputs of size $n > N$, evaluates $f_{\!\!\:n\!\:}$.
Having constructed $A$ in this way, each circuit family $\mathbf C^{(n)}$ fails to correctly decide $L_A$ with probability at least 2/3, for some $n > N$ (and infinitely many such $n$ in fact).
Then none of the circuit families $\mathbf C^{(k)}$ correctly decide $L_A$ with success probability bounded below by 2/3 on all inputs, so that $L_A$ cannot be solved with such bounds by any uniform unitary circuit family constructible in time $p(n)$.
Thus, $L_A \notin \mathsf{BQP}^A$, from which it follows that $\mathsf{NP}^A \not\subseteq \mathsf{BQP}^A$.
