Tracking down problems like these are a great opportunity to apply assertions. An assertion is simply a check on some boolean condition: "the set should be non-empty when
pop is called". Many programming languages provide direct support for assertions: when enabled, assertions will abort the program or raise exceptions when they fail; when disabled, assertions are nothing more than fancy comments.
This will take some digging and re-engineering on your part. You will need to scatter through the relevant parts of the program assertions that you believe are true. You may be surprised to see that some condition is failing, when you thought it was true. When a program does something like this, it introduces an infection [in the Andreas Zeller sense], which could then lead to further infections, which might finally manifest themselves as defects [bugs].
For more tips, read through Zeller's lecture notes from his fine book, Why Programs Fail: http://www.st.cs.uni-saarland.de/edu/adebug/2002/07-tracing.pdf
And here is a link to his discussion of assertions.
Finally, given that your client regularly encounters this, this first place to start is with them! Good luck!