without being able to reproduce the problem, it is impossible to be able to tell what may be causing it.
Where you cant reproduce the problem using the address they are entering, there must be something else they are entering that is trigger ing the problem.
That being said, I don't recommend using Client side validation since it is easily turned of by the user by disabling Javascript in the browser.
instead, i recommend using Server side validation. see the following thread for details on using server side validation with the ecart checkout form:
showthread.php?t=21834