If it's really important to keep the existing data which the user has entered so far, I'd say validation via ajax is going to be much easier than the "crazy loops" you mentioned. So this is really more of a javascript question than a perl question.

Using prototype.js (or if you know jquery) you basically make a regular form which has its onsubmit() handler set to make the ajax call and return false. So the browser won't attempt to change to another page. (Incidentally and off-topic, but for a good example, code like this is what the Rails function "form_remote_tag" auto-generates).

The perl side will be very minimal--just collect the params, validate them however you want and return some JSON with the rejected params, or with a flag indicating success. There are many examples of code like this to be found on the prototype mailing list (archived on google groups).