The elemental depletion of interstellar sulfur from the gas phase has been a recurring challenge for astrochemical models. Observations show that sulfur remains relatively non-depleted with respect to its cosmic value throughout the diffuse and translucent stages of an interstellar molecular cloud, but its gas-phase constituents cannot account for this cosmic value towards higher-density environments. We have attempted to address this issue by modeling the evolution of an interstellar cloud from its pristine state as a diffuse atomic cloud to a molecular environment of much higher density, using a gas/grain astrochem. code and an enhanced sulfur reaction network. A common gas/grain reaction network has been systematically updated and greatly extended based on previous lit. and models, with a focus on the grain chemistry and processes. A simple model was used to benchmark the resulting network updates, and the results of the model were compared to typical astronomical observations sourced from the literature. Our new gas/grain model is able to reproduce the elemental depletion of sulfur, whereby sulfur can be depleted from the gas-phase by two orders of magnitude, and this process may occur under dark cloud conditions if the cloud has a chemical age of at least 1 Myrs. The resulting mix of sulfur-bearing species on the grain ranges across all the most common chemical elements (H/C/N/O), not dissimilar to the molecules observed in cometary environments. Notably, this mixture is not dominated simply by H2S, unlike all other current astrochem. models. Despite our relatively simple physical model, most of the known gas-phase S-bearing molecular abundances are accurately reproduced under dense conditions, however they are not expected to be the primary molecular sinks of sulfur. Our model predicts that most of the missing sulfur is in the form of organo-sulfur species trapped on grains.