Blands knows what they're doing. Actually RT fares to GIB from London are fairly reasonable, including J fares which give good AA benefit. Otherwise you can pick the LCC of your choice to AGP and rent a car one way or probably there's a bus; you'd drop car/bus at La Linea and walk over the runway/border into GIB; taking a car into Gibraltar is madness. Actually getting out is the madness part.

As for other origin points, depends on your home > Europe access mode. ARN is pretty good for pricing and you could avoid the London shuffle (and BAA baggage mayhem if still extant) by going ARN-HEL-PEK... There also some LCC access to Stockholm too, or CPH and train...