All flights in Spain (inc. local) require a flight plan. As far as I am aware, any flight plan from a Spanish airfield to/from Gibraltar will not be accepted.
Flew with Aero Club Bahia de Malaga last summer. Highly recommended. Malaga's zone is huge and VFR flight is not above 1000' (watch out for the 3000'+ lumpy bits!) all the way to Marbella! Their fleet seemed pretty reasonable, however the 172 I rented had no altimeter on the P1 side!
Malaga ATC's English is interesting (glad I flew with instructor!), such as 'make good position' (?) when taxiing behind Easyjet 737. Also, there are a number of mandatory reporting points along the coast that are out of radio range due to the mountains; just make the call but don't expect a response!
Have fun.
140