I started my residency/DNI application whilst living in Spain, although I am a UK citizen.
It's a long process but achievable in the end. The criminal record aspect, correct me if I'm wrong is to confirm that your record is clear in your MAIN country of residence and the country from which you originate (UK in my case). I simply wrote to the Police HQ in the UK area I used to live, they sent me a form which i filled out and sent back. The reply was something like 'no records held pertaining to xxxxx' etc.
I'm sure your new wife will be able to assist you as did mine. There are agencies of course, but beware the fees.
Not much help really, but something.