Jezz,
Can't speak directly for Malta but a few years ago (2001 or 2002 I think) I went to Cyprus and hired a PA28 from Paphos after an hour's check ride with an instructor who showed me where I can and can't go etc. No problems at all. My (then CAA) PPL seemed to be well respected there. The logbook was fairly varied too.
If you drop someone a line out there they'll be able to let you know straight away. Have flown from Malta myself, was in the cruise by the end of the runway...