A norm-Euclidean domain is an Euclidean domain with respect to the norm function or the absolute value of the norm function. This implies that, for all $a,b \in R, b \neq 0$ where $R$ is a norm-Euclidean ring, we can find $q,r \in R$ such that $a=bq +r$ and either $r=0$ or $Norm(r)<Norm(b)$. I understand that Euclideanity of a domain implies the existence of such a $q,r$, however is there an analogue of the division function in the regular integers for general norm-Euclidean domains that can deterministically find $(q,r)$?
E.g. For norm-Euclidean imaginary quadratic rings, the problem is simple, as the algebraic norm coincides with the square of the Euclidean distance on a 2d graph, so finding $q$ corresponds to finding the closest lattice point on a 2d graph.
For complex quadratic fields, what you do, as you wrote, is set $q = NI(a/b)$, where $NI(\alpha)$ is the algebraic integer whose coefficients (with respect to the standard integral basis) are the nearest integers to the coefficients of $\alpha = a/b$.
The proof that a given number field is norm-Euclidean is in general constructive, so all you have to do is follow the proof.
If the number field was shown to be norm-Euclidean with the help of a computer, this will not be helpful. What you can do is consider all algebraic integers $q$ that differ not too much from $NI(a/b)$.
As the discriminants get larger, this is less and less likely to work. What you try then is check whether one of the quotients $q = NI(\epsilon \cdot a/b)$ for lots of units $\epsilon$ leads to a small remainder, because when it does then so will $r = a - b \cdot q \epsilon^{-1}$. But none of this is deterministic in general, except for number fields in which you have proved that this will work for specific units and specific choices of NI.
Thus there is a deterministic algorithm for each specific norm-Euclidean number field, but not for all norm-Euclidean fields.