Yes Jason, you are welcome here.
Peter is right. Essentially the main field is a no go for us, smaller GA folks. Last time I went there handling, landing fees about 388 euro. I guess the message is: bugger off, and go to the small field, Son Bonet (LESB). Off season you can use the main field for as many ILS approaches as you like, for free. Just make sure your wheels don't touch, else you will hear a very loud cash register on the radio :) Son Bonet indeed has no customs, so you need to come from somewhere Schengen.
On a different note: I am organizing a seaplane splash-in at LEPO, the beautiful Pollensa bay on the North East side of the island. 9-12 May. We are essentially fully booked, but I suppose I can handle one or two more. We are using the military base, Canadair water bombers there. Stay and food and entertainment paid for.. C'mon, this is a great deal! stick some floats under these planes of yours and join in! Strictly RSVP..
Majorca is very nice.
Their problem is they have two airports; one with avgas and no customs, and the other with customs and no avgas (and pricey) 
That looks a lovely place to fly. If I need to do an ICAO to EASA conversion I know where to go now!
Aart: that surely looks like heaven-on-earth. I still have Mallorca on my wishlist to visit.
Finally, and I know this will sound elitist, I would not worry about the odd k or two, because that will be insignificant on the scale of what flying costs in the long term. And if you are not into it long-term then don't bother because there won't even be any point in buying yourself a decent headset (£800).
Amen...
Find a plane that you would like to fly in future, and an instructor with some real experience and spend a bit more if needed.
As to accelerated learning.. Personally, I don't believe in learning to fly in a month. Yes, I understand that it sounds nice to be focussed and learn something in one go, but maybe it is better to take your time and let things sink in? Well, maybe we are all different and learn differently and I can only speak for myself..
Contributing to the options where to learn to fly (shameless plug, I am an instructor there), clearly below 7k GBP and with tremendous weather and scenery!
www.theaviationcentre.com/
I concur with Aeroplus above.
I love flying but found PPL training to be the most frustrating experience of my life, up to that point in time. So many cancelled lessons. So much un-enjoyable training (circuits, circuits, circuits, sweating like a pig) and then some stuff that should not happen (getting bumped off the lesson by a bunch of people, with enough body piercings to affect the W&B, who turned up for a pleasure flight... oops I meant a "trial lesson" 
)
In Oct Nov Dec 2000 I booked a flight every day i.e. 90 (ninety) lessons, and got just 3 done - warm front drizzle and gusty winds. Actually perhaps 80% of the days would have been flyable VFR, if you really wanted to go somewhere. I wasted 20hrs at one school with PA38s (in an appalling condition, water on the floor, ~ 0.5 litre of water on the tanks after a night of heavy rain because the school would not pay for replacing the filler cap seals, totally shagged elevator trims, yokes worn down to bare metal and corroded from years of sweat - and this was an AOC holder...) before realising this is a complete waste of my time and then starting almost again in C152s. Solo flights cancelled in the slightest haze (GPS? no way). If you can't see Bewlwater from 10nm, it's not flyable. It took me a year, and I was available almost every day.
It's a fair point that learning over time produces a more rounded pilot, but you waste a chunk of your rolling currency.
Also the UK training machine is very restricted in the knowledge that is transferred to the student. You only just barely learn to fly from A to B, where A and B are carefully chosen so that a monkey could find them. You learn nothing about what to do post-PPL, yet if you take out all those who do a PPL just to tick the "lifestyle achievement" box (say 50%), take out all those who obviously will never be able to afford to fly afterwards (say another 25%), take out those who are probably never going to enjoy it because, frankly, they struggled for 100hrs to get the PPL and don't even understand how a plane works (say 10%) what you are left with are the few who actually want to go places (or do aerobatics) and have the income and the personal circumstances (family support etc) to do it properly, yet those are not taught how to do what they paid their ~£10k for.
The other thing is that it is quite easy for a keep would-be pilot to get informal training. I did this a while ago with a very bright and motivated young lad. He passed all the exams before his first PPL lesson, and did the PPL in 45hrs (which is very rare where I trained). And a lot of people with aviation as a hobby could have considerable unlogged (legally unloggable) experience like that. When I first got into a plane I thought the ailerons were on the elevator! A family member of a competent pilot could easily learn the whole damn lot informally, and then just needs to pack the 45hrs in his logbook. I thought about doing the FAA CFI and training my son officially but EASA's "up yours to America idiots" have terminated that option.
In short, I think the PPL training scene is so far divorced from flying in the real world (which is done entirely on GPS, with navaids available as a backup) that it doesn't matter where you do the PPL. What matters is that you enjoy it, and don't waste money.
What ultimately matters is getting mentoring, not just post-PPL (which one is allowed to talk about, because schools are not really interested in you at that point, except for self fly hire) but also pre-PPL (which you can never mention to the school, for political reasons, and e.g. the UK AOPA mentoring scheme carefully works around that one). Doing some "normal" flights during the PPL training also keeps the student motivated because those flights can be fun. Actually the same applies to IR training...
The PPL theory is a more tricky topic because, unlike the JAA IR theory (which I found to be about 90% irrelevant drivel), you do actually have to know some of it. Quite how much is hard to say. perhaps 25%. But there is quite a bit which is not in the books or the exams and which is "operational" (e.g. a good idea to phone the airport before a flight, in case it is snowed in, etc, etc).
I have not done this myself and don't directly know anybody who has but I would feel that spending a month in Croatia or Greece, flying among the beautiful islands, would be really lovely - even if the people in the school look and talk like a load of time share salesmen from Lanzarote
France in the summer (Tumbleweed's post) could be the next best thing and potentially a lot better organised. Limoges is about the latitude below which you get decent wx in Europe.
Finally, and I know this will sound elitist, I would not worry about the odd k or two, because that will be insignificant on the scale of what flying costs in the long term. And if you are not into it long-term then don't bother because there won't even be any point in buying yourself a decent headset (£800).
Where I fly (West London Aero Club, White Waltham Airfield - EGLM) you can do a PPL for £8,126 in a PA28 or £7,847 if you don't mind flying a diesel-powered PA28.
Fees include 45hrs flying and all written exams. There are no home landing fees. You will need to join the club as a 'student member' - I can't recall what that costs but it isn't much.
Three 1000m grass runways - not the flattest, but wind direction is never a problem. Plenty of instructors (real ones with real experience - not just ATPL hour-builders) and plenty of aircraft.
If you want to get it done as quickly as possible then two major pointers:
Firstly - book some time off whatever it is you normally do during the week, make a lot of bookings, and really throw yourself into it. You will probably lose bookings to weather, so have plenty made. During spring, summer and autumn the weather is inevitably better later in the day: 6-8pm slots work really well during summer.
Secondly - stick with the same instructor 95% of the time, once you've found someone you get on with. Changing instructors inevitably slows things down while you get used to working with each other.
I did it in five months, flying weekday evenings and weekends. Remarkably, I didn't lose a single lesson to the weather in that whole time. I'm lucky in that I work nearby and weekday evenings were easy even at short notice.
And as Peter says, the absolute key is to do it in minimum hours. Whichever way you organise your schedule, 45hrs will always come before 60hrs!
I cannot speak highly enough of EGLM as a place to learn to fly. The amounts I quoted are from the website as of today, and assume payment up front. Conventional wisdom cautions strongly against up front payment because flying schools aren't the most stable of businesses, however two points to counter it in this case:
One - if you're doing it quickly then the period of exposure to risk is relatively short.
Two - West London Aero Club has been around forever and isn't going anywhere. The whole place is owned by someone mind-bogglingly rich who doesn't require the place to make a tidy profit - it just has to pay its way.
It is the same story as with learning how to swim. Here in Holland we take our children to swimming lessons when they are young. You spend months or even a year going each weak at the same night to the swimming pool with your child, help them getting ready and waiting for the swimming lesson to be over. Then, there is the "swimming exam" and they receive their diploma and basically know how to swim.
Here we found this swimmingpool in our hometown offering a crash-course where your youngster will learn how to swim from scratch and do the "swimming exam" in 5 consecutive days! Wow! I tried that with our oldest daughter, then did the same with the other 3 children and they all learned how to swim quite well in just 5 days while everyone around us thought it was not possible.
Same for the 7 PPL theory exams to take. Here in Holland there is this PPL Brainwash coarse that prepares you from scratch to taking all the 7 state exams in 1 week only. I did this and passed all the exams in one run.
As for the flying, I hated the many moments my flying lesson was cancelled and would have wished that I could have taken some PPL training course for 2-3 weeks in a row and get it over with.
Of course, after you are done, you actually still need to get experience flying in the real world, but I would not see why it is better for a student pilot to drive each week to the airport for one lesson (or for the lesson to be cancelled). There is also something valuable about focussing fully for a few weeks on one subject, to get it done and over with.
I decided to wait a bit before introducing this thread drift so the original question could be answered, but I dont agree with the intensive PPL route that can (assuming perfect weather) produce a qualified pilot in a matter of weeks. Worse, when it is undertaken in a country with weather, ATC communication and terrain unlike the base location of the pilot.
I'm not saying a PPL should always take 1 year, but I think it should be done over a minimum of 3 months, even for those going straight onto ATPL training. I think to be a safe pilot at any level, one needs more than just few weeks of knowledge cramming, and flying experience. You need time to relate the theory and the practicality of flying. I also think one needs to experience different weather conditions and the experience of comparing METAR's and TAF's to what actually happened on the day to aid better go/no-go decision making. Maybe in that 3 months there might be the odd aircraft fault (minor hopefully) or some other life lesson that gives a PPL a good grounding.
Let's be realistic - the British weather will bugger all but the luckiest people trying to do any licence course quickly, particularly a PPL, which is the most weather dependent of all licences.
Spain, Florida, California, South Africa - they have weather that will give a fighting chance of a quick PPL. They'll also not teach anybody how to fly in British weather, with British airspace and British ATC - so some re-training will be needed on returning home.
But there is mileage in that, given that the licence can be done quickly and relatively cheaply in those places - cheaply because the instructors and aeroplanes get much more use every day, and so per hour can be cheaper. Quickly for the same reasons.
G
