The question is essentialy the title: is there a smooth algebraic surface $X$, say over $\mathbb{C}$, and an irreducible algebraic rigid curve $C\subset X$ with non-negative self intersection?
Here by rigid I mean that $h^0(X,C)=1$, so the only effective divisor linearly equivalent to $C$ is $C$ itself.
The only examples of rigid curves I know have negative self intersection.
Observations
I'm pretty sure that the answer is negative for del Pezzo or K3 surfaces. Indeed, for del Pezzo we have
$\chi(X)= 1$ being $h^1(X,\mathcal{O}_X)=h^2(X,\mathcal{O}_X)= 0$,
$-K_X\cdot C> 0$ being $-K_X$ ample
$h^2(X,C)=h^0(X,K_X-C)=0$, using Serre duality.
Therefore, by Riemann-Roch we get $$h^0(X,C)=h^1(X,C)+\chi(X)+\frac{1}{2}C^2-\frac{1}{2} K_X\cdot C> 1+\frac{1}{2} C^2$$
so $h^0(X,C)>1$ if $C^2\geq 0$.
A similar computation holds, with some differences, for K3 surfaces.
Therefore, I tried to work on hypersurfaces of high degree in $\mathbb{P}^3$ but couldn't find such a curve.
Here is a simple example. Take an elliptic curve $C$ so $H^1(O_C)$ is one dimensional. Thus we have a non-split exact sequence $0\to O\to E\to O\to 0$. This section gives a section $D$ of $\pi:\mathbb{P}(E)\to C$ with $D^2=0$. $\pi_* O(D)=E$ and so $h^0(O(D))=1$, showing that $D$ is rigid.