Your bank is actually completely correct. The problem is at the UK end!
Basically in the UK Switch was their national debit card scheme and operated much like Laser, a closed network.
Maestro is normally an international debit card, and many European debit cards carry the Maestro logo and should be acceptable over-the-counter without any problems.
However, in the UK, Switch was fully rebranded as Maestro. However, the transactions are still processed by the old Switch network. It's causing a lot of confusion and it's really stupid on the part of Maestro.
It means that some UK retailers can't accept non UK issued Maestro cards at all and that online sites can only accept UK issued cards (as they don't really accept Maestro at all, but rather re-branded switch!)
Tesco's terminals regularly seem to screw up. I've had them refuse perfectly valid credit cards, debit cards etc. It's usually nothing more than a dirty chip and pin reader that's the problem. Those machines, particularly in a supermarket, take a lot of abuse.
If your card's also a Laser card, there's absolutely no reason why Wallis in the Republic of Ireland shouldn't accept it. Contact your bank. It sounds like there's either a problem with your card, or with the Wallis terminals.
It's nothing to do with it being a Maestro.