(By "norm" here I mean "absolute value of the norm)"
Are their infinitely many such pairs or is it finite in the sense that its just a few primes that cause the problem (like in that other famous Euclidean but not norm-Euclidean domain)?
I've tried searching for these pairs by looking at numbers with small norms, but of course I know this is woefully inefficient. I think I've found one such pair: $\gcd(3, 3 + \sqrt{14})$. Then $1 \times 3 + \sqrt{14} = 3 + \sqrt{14}$ but $|N(\sqrt{14})| > N(3)$, and in general it seems like any rational multiple of $3$ will result in a remainder with a norm too large. Clearly I'm in need of some theoretical insight, such as perhaps with ideals.