From your problem description, I assume the $x_i$ from the first two paragraphs are what is called $r_i$ later. I do not yet have a complete answer, but would like to point out some observations and ideas (sorry, I'm not allowed to write comments yet):
It seems to me that we can, without loss of generality, assume the $x_i$ to be commensurable. Otherwise, split $S\in\mathbb{Z}[x_1,\dots,x_n]$ into a representation wrt a basis of $\mathbb{Z}[x_1,\dots,x_n]$.
Thus, by multiplying through with a suitable constant, we can assume that the $x_i$ are positive integers. We may also assume $\gcd(x_1,\dots,x_n)=1$, since otherwise, any $S$ for which the equation has a solution is also divisible by this gcd, which allows dividing the whole equation. Edit: Both of these simplifying assumptions shift the set of solutions (to solutions for some other $S$ and $r_1,\dots,r_n$, but in a bijective way.
The number of solutions for any particular $S$ and $x_1,\dots,x_n$ can be counted using generating functions (similar to Polya's method for counting possibilities of giving change); with your example $S=98\,a_1+99\,a_2$ and $0 \leq a_1,a_2 \leq 100$, the number of solutions for $S$ is the coefficient of $x^S$ in the polynomial $(x^{98}+x^{2\cdot98}+\cdots+x^{100\cdot98})\,(x^{99}+x^{2\cdot99}+\cdots+x^{100\cdot99})$, whose lowest exponent with coefficient larger than $1$ is $9899$.
I'm not sure I've got a good way of explaining this. Essentially, the first of these polynomials is the generating function for the number of solutions for $S=98\,a_1$ and the second is the generating function for the number of solutions for $S=99\,a_2$. Since in these generating functions, the $S$ values are in the exponents, summation of the $S$ values corresponds to multiplication.
If you wanted to write a computer program to find the smallest $S$ such that the corresponding coefficient in the generating function as given above fulfills some condition (e.g., is larger than $1$), it would probably be a good idea to use standard written multiplication and use a heap structure for carrying out the steps. Such an implementation would provide a stream of coefficient/exponent pairs and can also use such as one of its two inputs, which means that the multiplication of very many polynomials can be performed with little memory overhead, especially without needing to store all the coefficients already checked and found not interesting, and the calculation can stop almost without computing anything beyond the first “interesting” term.