It is highly unlikely that Plusnet is running an open mail relay. Everybody with one of those gets blacklisted pretty fast, and Plusnet is a big ISP.
I've known big ISPs get blacklisted but they always sorted it out very quickly. Yahoo have often blacklisted ISPs and the ISP had to sort that out pretty fast!
From what you say I'd suggest the problem is your customer's ISP. Nowadays, literally anybody can be an ISP. For about £10k/year I could get a 2meg DSL line to my spare bedroom and run a server in there.