Let $S$ be a surface in $\mathbb{R}^3$. I believe that, if $S$ is smooth, bounded, and closed, then, for every pair of points $x,y \in S$, there is at least one geodesic $\gamma$ connecting $x$ to $y$. This is because there is certainly a path between $x$ and $y$, and then one could shorten it until it is locally shortest and is then a geodesic.
Q1. Is this correct?
If so:
Q2. What are examples of surfaces $S$—perhaps not smooth, not bounded, and/or not closed— for which not every pair of points is connected by a geodesic?
Any smooth surface in $\mathbb R^3$ that is a closed subset of $\mathbb R^3$ is complete as a metric space. Thus, if it is also connected, the Hopf-Rinow theorem guarantees that it is geodesically complete, which in turn implies that any two points can be connected by a minimizing geodesic.
Therefore, the only ways that geodesic completeness can fail are
This means that for connected surfaces, in a certain sense the only way for geodesic completeness to fail is if one or more points are "missing." More precisely, if $S$ is connected but not geodesically complete, then it's not closed, which implies that there's a sequence of points $p_n\in S$ that converges to a point $q\in \mathbb R^3\smallsetminus S$. You can think of $q$ as a point that "should be" in $S$ but isn't. (But this doesn't imply that there was originally a smooth surface from which $q$ was removed -- for example, $S$ could be the cone $x^2 + y^2 = z^2$ with the origin removed.)