Is it better to give the user instant feedback that a field is invalid on keypress, or should you wait until they blur the field? The first option might annoy users if they are told their input is invalid before they've finished typing. The second could annoy users if they have to refocus a field. Perhaps a solution is to display validity/completeness (green) in real time, while delaying the display of erroneous validation until blur?
Validate on blur, or on submit. Don't validate while typing, for exactly the reason you describe.
There are studies/observations that show the people generally complete the entire form and then return to values that are incorrect. Even if you validate on blur they will tend to complete all fields and will then return to fix.
The study alone suggests you should present error after the user has completed the form -- in other words, on submit.
If you validate on blur, show a simple non-obtrusive error (a highlight and possible a short message next to or under the field). Do not force the user to fix it immediately. You can disable the "submit" button until all fields are validated -- include a small message or popover indicating why the "submit" button is disabled (e.g., "Please fix the highlighted fields before submitting"). You can let the user submit despite errors too and display an additional error message then.
Validating on blur helps the user realize something is wrong before they submit, but you will also need to validate on submit to make absolutely sure everything is formatted the way you want it. However, the study quoted above would suggest that validating on blur does not buy you anything that validating on submit already provides.
As revealed in this fantastic article, the answer is on blur.