Shortest orthogonal integer vectors and their cross product 
Question:
  Given an arbitrary non-zero vector $v \in \mathbb{Z}^3$ with $\gcd(v) = 1$, there exist linear independent non-zero vectors $f, s \in \mathbb{Z}^3$ orthogonal to $v$ and minimal with respect to the Euclidean norm. Their cross product must be a scalar multiple of $v$, say $f \times s = \lambda v$. Obviously $\lambda \in \mathbb{Z}$, but is $\lambda = \pm 1$?

With help from Rodrigo de Azevedo I made progress.
This answer provably provides two basis vectors spanning the lattice of vectors orthogonal to $v$.
Then an algorithm due to Lagrange finds the shortest two basis vectors $f$ and $s$, given any two basis vectors $b$ and $c$ :  

if $\lVert b \rVert < \lVert c \rVert$:
  $\quad$ $b, c := c, b$
  while $\lVert c \rVert < \lVert b \rVert$:
  $\quad$ $b, c := c, b - \lfloor \frac{\langle\,b,c\,\rangle }{{\lVert c \rVert}^2}\, \rceil c$
  return $b, c$
Here $\lVert \cdot \rVert$ denotes the Euclidean norm, $\lfloor \cdot \rceil$ the nearest integer function and $\langle\,\cdot, \cdot\,\rangle$ the dot product.

On my computer checking 10000 random vectors takes roughly 5 minutes. So far I haven't found a counterexample.
Motivation:
Consider the homogeneous diophantine equation
$$v_1x_1+v_2x_2+v_3x_3=0$$
over $\mathbb{Z}$ with $v$ given and $\gcd(v)=1$.
A version of Siegel's lemma states, that there exist two non-trivial linear independent solutions $f, s$, such that 
$$\max(|f_i|) \max(|s_i|) \leq \lVert v \rVert. $$
Since
$$|\lambda| \lVert v \rVert = \lVert f \times s \rVert \leq  \lVert f \rVert \lVert s \rVert < 3 \max(|f_i|) \max(|s_i|) \leq 3 \lVert v \rVert,$$
we have $|\lambda| \leq 2$. I was hoping for either an example with $|\lambda| = 2$ or an intuitive explanation why $|\lambda|$ always equals $1$.
 A: As an extension to the Rodrigo de Azevedo's answer, it must be mentioned that the $b_1$ and $b_2$ vectors, selected as $(-v_2,v_1,0)$ and $(-v_3,0,v_1)$, do not generally produce the right results by just using the lattice reduction. To generate correct source vectors for that purpose, it is needed to first find out 2 integers $p$ and $q$ so that $p v_2+q v_3 = GCD(v_2,v_3) v_1$. This can be made by applying GCD method, and produces two different solutions $(p_1,q_1)$ and $(p_2,q_2)$, when $|p_i|<v_3$ and $|q_i|<v_2$. In fact, if $p_1 > 0$ and $q_1 < 0$, then $p_2 = p_1 - v_3 < 0$ and $q_2 = q_1 + v_2 > 0$. Then you calculate new $b_1' = (p_1 b_1+q_1 b_2)/v_1$ and $b_2' = (p_2 b_1+q_2 b_2)/v_1$. The division is possible because all the corresponding values are multiples of $v_1$. The lattice reduction may now be performed using $b_1'$ and $b_2'$, and assumedly produces the right results. (Note that in the practical example (1,2,3) this extra step was avoided by using $v_1$ = 1).
Let us consider a general case $(v_1,v_2,v_3) = (aef,bdf,cde)$, where $a$, $b$, $c$, $d$, $e$, and $f$ are positive integers having no pairwise common factors. We note that $GCD(v_2,v_3) = d$, $GCD(v_1,v_3) = e$, and $GCD(v_1,v_2) = f$, but $GCD(v_1,v_2,v_3) = 1$. We get $b_1 = (bd,-ae,0)$ and $b_2 = (cd,0,-af)$, where we have divided the values with their common factors $f$ and $e$, respectively. Now we find out $p$ and $q$ so that $pb + qc = a$, where $0 < p < c$ and $0 < |q| < b$. The candidates for shortest orthogonals are then $b_1'= (pb_1+qb_2)/a = (d,-pe,-qf)$ and $b_2'=((p-c)b_1+(q+b)b_2)/a = (d,-(p-c)e,-(q+b)f)$. Both are orthogonal to $(v_1,v_2,v_3)$ and $b_1' × b_2'  = (ef(pb+qc),bdf,cde) = (aef,bdf,cde) = (v_1,v_2,v_3)$. This candidate pair thus fulfills the condition $λ=±1$.
Note that by exchanging the roles of $v_1$, $v_2$, and $v_3$ we (may) get more candidate pairs, which may (or may not) be even shorter, but still fulfilling the condition $λ=±1$.
