Pick from each small rectangle a parallel pair of sides whose length is in S (arbitrarily, if both pairs are compliant). These will be the edges of the graph. We note that this is really a multigraph: a pair of vertices may have two parallel edges connecting them.
Now, begin at a corner and travel along the graph's edges as much as you can without using the same edge twice. The point you will get stuck in is another corner. The way to see it is that all other vertices have an even number of rectangles associated with them, and therefore an even number of edges.
Throughout, every motion in either axis was by an amount in S. Therefore, the total distance traveled in each axis is in S. Because we traveled from one corner of the large rectangle to another, this completes the proof.
Q.E.D.
As mentioned, Graham Hemsley sent me this riddle. He reached this solution independently, as well as the formulation of the riddle variant. Stan Wagon credits this solution to Michael S. Paterson of the University of Warwick. It appears here, in his classic compendium of fourteen proofs to the classic rectangle tiling problem, as proof number 7. I thank Oded Margalit for directing this beautiful riddle variation my way.