Is every proper regular relative algebraic space curve over a Dedekind domain projective?

Yes. The task is to show that $X$ is a scheme (as then Lichtenbaum's result may be applied). By standard "spreading out" arguments, we may assume $S = {rm{Spec}}(R)$ for a discrete valuation ring $R$, say with fraction field $K$, residue field $k$, and maximal ideal $mathfrak{m}$. The special fiber $X_k$ is a scheme. Let ${C_1, dots, C_n}$ be the irreducible components of $X_k$ (say with reduced structure).

Let $x_i in C_i$ be a closed point, and let $U_i rightarrow X$ be a residually trivial etale affine neighborhood of $x_i$ that is a scheme, so $U_i$ is a regular affine $R$-curve (i.e., flat finite type over $R$ with fibers of pure dimension 1). We may shrink $U_i$ so that its special fiber misses each $k$-finite $C_i cap C_j$ for $i ne j$, which is to say that $(U_i)_k$ lands in $C_i$. By going-down for flat morphisms, applied to $R rightarrow O_{U_i,x_i}$, we can choose a closed point $u_i in (U_i)_K$ whose closure in $U_i$ contains $x_i$. Thus, the image $xi_i in X_K$ is a closed point whose closure in $X$ contains $x_i$.

Since $X$ is regular of pure relative dimension 1 over $R$, the closure $D_i$ of $xi_i$ in $X$ has invertible ideal sheaf $mathscr{I}_{D_i}$. (Indeed, such invertibility may be checked on an etale scheme cover of $X$, where it becomes the fact that a height-1 prime in a regular domain in invertible, as regular local rings are UFD's.)

Let $mathscr{L}$ denote the tensor product of the inverse sheaves $mathscr{I}_{D_i}^{-1}$. Since each $D_i$ is $R$-flat, the formation of $mathscr{L}$ commutes with base change on $R$, such as passage to the special fiber. By the theory of algebraic curves, $mathscr{L}_k$ is thereby seen to be ample on $X_k$. Hence, for any coherent sheaf $mathscr{F}$ on $X$, for all sufficiently large $m$ we have that $mathscr{F} otimes mathscr{L}^m$ has vanishing degree-1 cohomology on $X_k$.

If $mathscr{F}$ is $R$-flat and $pi in R$ is a uniformizer then we have a short exact sequence $$0 rightarrow mathscr{F} otimes mathscr{L}^m stackrel{pi}{rightarrow} mathscr{F} otimes mathscr{L}^m rightarrow mathscr{F}_k otimes mathscr{L}_k^m rightarrow 0$$ whose associated cohomology sequence gives the vanishing of ${rm{H}}^1(X, mathscr{F} otimes mathscr{L}^m)=0$ for such large $m$ (due to Nakayama and $R$-finiteness of this H$^1$). Applying this with $mathscr{F}$ equal to the ideal sheaf on $X$ of a (varying) closed point of $X_k$, we see that for some large $m_0$ the line bundle $mathscr{L}^{m_0}$ is generated by global sections. By replacing $m_0$ with a big multiple, the formation of the $R$-finite (free) module of global sections commutes with reduction modulo $mathfrak{m}$.

Now we get a natural $R$-map $f:X rightarrow {rm{Proj}}(Gamma(R, mathscr{L}^{m_0}))$ whose formation commutes with reduction modulo $mathfrak{m}$, and on the special fiber it is quasi-finite since $mathscr{L}_k$ is ample on $X_k$ with $m_0$th-power generated by global sections. For any map of finite type between noetherian algebraic spaces, the quasi-finite locus is open on the source (as may be checked etale-locally, where it reduces to the known analogue for schemes), so the open quasi-finite locus $U subset X$ of $f$ contains $X_k$. But $X$ is $R$-proper, so this forces $U=X$. Hence, $f$ exhibits $X$ as separated and quasi-finite over a scheme, so $X$ is a scheme (by a theorem of Knutson).

[The preceding is not optimal, since the conclusion that $X$ is a scheme, even quasi-projective, should be true with "proper" relaxed to "separated, flat, and finite type".