Flexihosting blacklisted by Barracuda?

[eclipse]

Hi all,
we've had a few clients tell us they can't get emails etc because our email goes through our domain name with our business site hosted by Flexihosting.

3 clients can't accept our emails because Barracuda is cranky with Flexihosting.

Any ideas?

I've got 6 months left with Flexihosting, but may have to move early because of this.

 

[ChicoWeb]

Are they all on the shared IP? Perhaps you can request a new IP.