Save Commerce Order and Customer Profile on validation fail
You can can implement hook_form_alter in your custom module and add one more validation handler on top of validation handlers stack, so your is called first.

Inside your validation function follow the way the module Commerce Postal Code Filter is putting the validation, I assume it should be as simple as calling a function. Now if depending on what value it returns you can programmatially update current order status.