show/hide this revision's text 2 |Delta| ==> Vol(Delta)

Hermite normal form (HNF) should work much as you suggest.

Translate $v_0$ to 0. Let $L = \bigoplus_{i=1}^n {\bf Z} v_i$. HNF gives an explicit decomposition of $G := {\bf Z}^n / L$ as a direct sum of cyclic groups. Both the computation and the resulting generators take time polynomial in the input size. This lets you run through representatives of the $|G|$ cosets of $L$ in ${\bf Z}^n$. Write each one uniquely as $\sum_{i=1}^n a_i v_i$ for some rational $a_i \in {\bf Q}$. Replacing each $a_i$ by its fractional part $\{ a_i \} = a_i - \lfloor a_i \rfloor$ gives the only candidate for the intersection of the coset with $\Delta$, which works iff $\sum_i \{ a_i \} \leq 1$. (Exception: the trivial coset has $n+1$ representatives, but you already know them: $0$ and the $v_i$.) The processing time per coset is again polynomial in the input size, and the number of cosets is $|G| = n! {\rm Vol}(\Delta)$; since for you $n$ is fixed, this answers your question.

Along the way we've obtained $|\Delta \cap {\bf Z}^n| \leq n! |\Delta| {\rm Vol}(\Delta) + n$, giving (again for fixed $n$) the result you "haven't been able to extract yet from the literature", with explicit constants. Equality holds at least when $n! |\Delta| = 1$.

I haven't yet given or cited a proof that HNF can in fact be computed in time polynomial in input size. This seems clear, though the first thing one might try may produce an algorithm that's too slow in practice. A brief Google search indicates that (not surprisingly) there has been considerable work on this question; one article that turns up often is "Asymptotically Fast Computation of the Hermite Normal Form of an Integer Matrix" by Arne Storjohann and George Labahn (1996), which gives bounds whose dependence on $n$ is polynomial as well (in particular the exponent does not depend on $n$). There's also an HNF implementation in gp with several variations, see mathnf — that's MATrix HNF, not MATH something :-) — and probably other packages do this too. You might also try Smith normal form (matsnf), which seems to do much the same thing for this purpose.
show/hide this revision's text 1

Hermite normal form (HNF) should work much as you suggest.

Translate $v_0$ to 0. Let $L = \bigoplus_{i=1}^n {\bf Z} v_i$. HNF gives an explicit decomposition of $G := {\bf Z}^n / L$ as a direct sum of cyclic groups. Both the computation and the resulting generators take time polynomial in the input size. This lets you run through representatives of the $|G|$ cosets of $L$ in ${\bf Z}^n$. Write each one uniquely as $\sum_{i=1}^n a_i v_i$ for some rational $a_i \in {\bf Q}$. Replacing each $a_i$ by its fractional part $\{ a_i \} = a_i - \lfloor a_i \rfloor$ gives the only candidate for the intersection of the coset with $\Delta$, which works iff $\sum_i \{ a_i \} \leq 1$. (Exception: the trivial coset has $n+1$ representatives, but you already know them: $0$ and the $v_i$.) The processing time per coset is again polynomial in the input size, and the number of cosets is $|G| = n! {\rm Vol}(\Delta)$; since for you $n$ is fixed, this answers your question.

Along the way we've obtained $|\Delta \cap {\bf Z}^n| \leq n! |\Delta| + n$, giving (again for fixed $n$) the result you "haven't been able to extract yet from the literature", with explicit constants. Equality holds at least when $n! |\Delta| = 1$.

I haven't yet given or cited a proof that HNF can in fact be computed in time polynomial in input size. This seems clear, though the first thing one might try may produce an algorithm that's too slow in practice. A brief Google search indicates that (not surprisingly) there has been considerable work on this question; one article that turns up often is "Asymptotically Fast Computation of the Hermite Normal Form of an Integer Matrix" by Arne Storjohann and George Labahn (1996), which gives bounds whose dependence on $n$ is polynomial as well (in particular the exponent does not depend on $n$). There's also an HNF implementation in gp with several variations, see mathnf — that's MATrix HNF, not MATH something :-) — and probably other packages do this too. You might also try Smith normal form (matsnf), which seems to do much the same thing for this purpose.