The links I have sought out have only been from sites with some related interest - either other towns nearby or Spanish travel or expat sites.
That ought to pass muster with Google (no penalty). My assumption is that at some point a real human looks over a site and manually "adjusts" a machine-generated list of keywords, and that list is used to compare (by machine) against other sites and decide if they're "related" enough. At least, that's what I'd guess that Google does. Maybe they're confident enough in their AI skills to do it all by computer (humans out of the loop) and the keywords just aren't matching up well enough. Remember too that Google (and possibly the other engines) are constantly changing their ranking systems as people learn how they work and starting "gaming" the system.
That's part of the problem - finding enough suitable sites to link to. I deliberately avoided signing up to any link exchange programs, simply because I can't see the point of having a page full of unrelated links on my own site.
As I said, Google (and perhaps other search engines) will penalize you if it thinks your inbound links are coming from a junk (unrelated) site that's just trying to pump up search result rankings with lots of bogus links.
Don't quite understand your last sentence. I've been looking for sites to reciprocate links, but within the pages of my site I have occasionally put in a useful link (for example to tourist attractions). Should I be including my own url somehow in those links?
No, that's not what I was getting at. My suggestion was that if someone says, "paste this link code to my site into your site and in 21 days you will receive 100 inbound links in return" (sounds like a chain letter, doesn't it?), check to make sure that the link to them has a URL query string with something about
you. A link like
<a href="http://www.theothersite.com">The Other Site</a>may help
them (if sites have similar business), but doesn't necessarily have anything to help them create a link back to
you. On the other hand, if the resulting link is something like
<a href="http://www.theothersite.com/links.php?mysite=http://www.mysite.com&myarea=spain+city+torremolinos+...">The Other Site</a>they have the information at hand to make a link back to you. (Yes, I know, some of the punctuation in the UQS needs to be escaped with %xx hex codes.) Now that I think about it, there might be other ways to accomplish this (HTTP REFERER?). At any rate, check them out after the promised length of time and see if they ever did get around to creating a link back to you. Be sure to "exercise" those links once or twice to make sure that they actually
do get a hit from you (and get the information to make a link back).
Finally, don't forget to do all the other things that can lead to good rankings: important keywords in domain name, page titles, keyword and description meta tags, headers, body text, image alt and title attributes, etc. Text, not graphics! A spider has to be able to read everything and have it make sense. There's more to search engine rankings than just inbound links.