Hi Jaipur_Mart,
Well just saw your this post and wish to ask if you have resolved this issue ?
Or if not, then let us simply point out that you can request the customer to add this address in their paypal or rather in their Ebay Address, so a specific email with the change in address request from the buyer's side can be recieved from you in your Ebay Messages. So then this can be kept in your handy reference to proove that ONLY after the customer's VALID request, you have shipped to his OTHER SPAIN address. You can have lot of GENUINE customers actually making such requests, so there is nothing wrong, do not forget to check the Customer's EBAY PROFILE and feedback score.
One last thing, Customers or users of PayPal, OUtside US are generally NOT Verified untill they have a lot of Paypal Score and Payments made or recieved...so that is NOT SO MUCH a problem.
Check these little details and let us know if you need any further assistance.
Hope this helps.
- The Cyberwiz
Anchanting_Kolors