In reply to Scrabble: I stayed here in May :
http://www.travelrepublic.co.uk/hotels/spain/majorca_puerto_pollensa/cheap_...
Booked through travelrepublic and it was really cheap. Apartments are perfectly good - cheap and cheerful but clean and functional. Bar downstairs that does food if you want it, there's also a couple of pools and all have balconies. Transfer from the airport was £16 return but with a couple of you might be worth getting a car. Buses run from outside the hotel though, so getting around isn't hard. I hired a bike for the week instead and that was ace!
Puerto Pollensa is a small and decent resort, not as trashy as elsewhere, nice places to eat and drink. You can walk from the hotel to do the awesome Cavall Bernat Ridge. Also some climbing up behind the village.
I got some really good ideas from lovely UKC people here:
http://www.ukclimbing.com/forums/t.php?t=550632&v=1#x7356416
Have fun!
Co: