I have just returned a Avis car here in TFS and having read your post I spoke to the staff here as I am due to have an Avis car in Malta as a BA Holiday.

I was told that until recently they also closed at 8pm but things are back to normal and they now close at 11pm. I was assured that it would be the same in Malta and no surcharge if you arrive before 11pm. See that my flight arrives at 9pm.
As a separate issue at TFS Avis Bus you to their rental centre and finding bus stop nos 6 in no easy task.

s