what exactly are they not allowing? i don't see why they'd have a problem with malta itself. you could also look into kraken.com. that's in the sepa zone too.
They will not allow an account under the Malta name, but my personal name only. This means that I have the tax obligation, and not the company. This causes me to comingle funds that should be exclusively for the business.
Would localbitcoins be an option?
I'm sure there are a number of sellers that operate from Malta, offering about any payment method you can think of.
That's a great idea. I will check them out.