This Python script computes S_n for n from 1 to 4 correctly using my algorithm. It was somewhat fun to fiddle with higher order iteration, but the extremely naive method I've used becomes too inefficient for larger values, since it does a very poor job of brute forcing Step 3. I had hoped to use it to compute the next few terms, though I'll need to modify that section to make it complete in a reasonable amount of time. Without doing that at the moment, using Logophobic's number for S_5, we seem to have found this sequence with several combinatorial interpretations. That page lists several formulas for computing this series, including...

S_1=1
S_n = -(n-1) * S_(n-1) + Sum_{k=1..n-1} binomial(n, k) * S_k * S_(n-k)

In any case, this allows us to easily compute (what almost certainly is) our sequence. The original context of this problem was to compare the number of unique formulas of the above type (including subtraction, actually) to n!. Computing the n=2 to 20 terms, the ratio of 2*S_n to n! is (rounded to two significant figures):
1.0, 1.3, 2.2, 3.9, 7.6, 45, 16, 33, 71, 160, 350, 790, 1800, 4200, 9700, 23000, 54000, 130000, 300000, 730000

Obviously the number of formulas greatly exceeds n! for large n; the original question involving even more general formulas is certainly hopeless without a better accounting of equivalences in the particular modular arithmetic case in question. Incidentally, the ratio of these fractions is relatively constant and seems to stabilize under 3, likely to a constant that I cannot identify. In any case this thread's question has been answered to my satisfaction and the potential proof technique that started this one has been basically disproved, so I'm satisfied. My thirst for combinatorial explorations is also temporarily satisified.

Thanks Logo! You should be "Logophilic".