I traveled through southern Spain in 2012 and purchased a pre-paid SIM card from http://www.simcardspain.es/en/ They also sell on eBay. They were very responsive to email when I asked which SIM would be best for the region I was traveling through. Once purchased I believe I had to email them my passport number etc. so they could activate the card. Worked out very well especially since it was activated and ready to go once we landed in Madrid.