Unless you are setting up individual VPS plans for each business you serve, you should only need 1 IP for the mail server to send these messages. Even with each business running on a VPS, you would still only need 1 IP per VPS for mail and based on my experience, I doubt you would be setting up 128 VPS plans on this server. If you could provide further explanation for the IP requirement it might help your case.
I find the whole talk about "long term relationship" weird. I mean, who goes in saying "I want a long term relationship with a host" ? The only time I've ever seen that is when the exact opposite is true. Actually, I do have one customer who paid a year in advance who wanted a long term hosting relationship, that was legit.