It seems to me that the standard definition of the Riemann-Stieltjes integral is too strict as to almost never exist.
First, I want to recall the definition of the Riemann-Stieltjes integral, which I am taking from Wheeden-Zygmund page 23. $\int_a^b f d\phi = S$ is defined to mean $\displaystyle{\lim_{\|\Gamma \| \rightarrow 0} \sum_{\Gamma} f d\phi } = S$, where $\Gamma = \{ (t_i)_{i=1}^N, (x_i)_{i=0}^N\} $ is a tagged partition of $[a, b]$ and $\displaystyle{\sum_{\Gamma} f d\phi} = \displaystyle{\sum_{i=0}^N f(t_i)(\phi(x_{i+1}) - \phi(x{i}))}$ and $\|\Gamma \| = \text{min}\{ x_{i+1} - x_{i} \}_{i = 0}^{N-1}$.
Now, let's take the standard example of a probability mass function, which can also be found on page 23. Let $\phi$ be a step function that is constant on $(\alpha_{i-1}, \alpha_i)$ for $i = 1, \ldots, m$ where $a = \alpha_0 < \alpha_1 < \ldots < \alpha_m = b$ for some $\alpha_i's$. Let $d_i = \phi(\alpha_i+) - \phi(\alpha_i-)$ for $i = 1, \ldots, m-1$, where +, - denote the right and left hand limits, and let $d_0 = \phi(\alpha_0+) - \phi(\alpha_0)$ and $d_m = \phi(\alpha_m) - \phi(\alpha_m-)$. Now, consider a sequence $\Gamma_k$ of tagged partitions such that $\| \Gamma_k \| < \frac{1}{k}$ and each $\alpha_i$ are endpoints of some interval in $\Gamma_k$ for each $k$. It follows that $\displaystyle{\sum_{\Gamma_k} f d\phi } = 0$ for every $k$ since the $d\phi = 0 $ on each interval of each $\Gamma_k$. Let $\Gamma_k'$ be another sequence of tagged partitions such that $\| \Gamma_k' \| < \frac{1}{k}$ for each $k$, and each $\alpha_i$ is included in intervals in $\Gamma_k$ with tag $f(\alpha_i)$. It then follows that $\displaystyle{\sum_{\Gamma_k'} f d\phi } = \sum_{i=0}^m f(\alpha_i) d_i$ for every $k$.
The existence of the Riemann-Stieltjes integral implies that for $\textit{any }$ sequence of tagged partitions $(\Gamma_k)_{k=0}^\infty$ such that $\|\Gamma \| \rightarrow 0$, $\displaystyle{\sum_{\Gamma_k} f d\phi } \rightarrow S$. However, we see that $\displaystyle{\sum_{\Gamma_k} f d\phi } \rightarrow 0$ and $\displaystyle{\sum_{\Gamma_k'} f d\phi } \rightarrow \sum_{i=0}^m f(\alpha_i) d_i$, so the Riemann-Stieltjes integral does not exist in this case. This is, of course, the standard case of a probability mass function, so it should indeed be integrable.
This is a classical theorem that includes the classic Riemann integral existence theorem as a special case, which is: $\int_a^b fdx$ exists as a Riemann integral iff the set of discontinuities of $f$ is of $0$ measure.
Theorem (Riemann-Stieltjes Integral Existence): Let $f$ and $g$ be bounded real functions on $[a,b]$, and suppose that $g$ is non-decreasing on $[a,b]$. Then $f$ is Riemann-Stieltjes integrable with respect to $g$ iff the set of discontinuities of $f$ is of $g$-measure zero.
In particular, if $g$ has a jump discontinuity at $x \in [a,b]$, then $f$ cannot have a discontinuity at $x$ in order for the Riemann-Stieltjes integal $\int_a^b fdg$ to exist.