How do I get around restrictive email policies by ISP?

get vps / cheap dedicated server and set up smtp relay there. use alternative port for smtp [ in worst case even 443 although traffic you'll sent will be smtp ].

remember not to set up open relay - filter based on src ip addres - that would be ip address of your server at current isp. i'm doing this kind of set-up for mass mailing, mostly because ips of shared web hosting i use in one case are blacklisted.

Move to an ISP that supports the type of traffic you want to generate.

Get some hosted email service that does what you want. Seems fairly straightforward to me.

Edit:

"Hosted email" means a whole spectrum of offerings, from the very simple to the very complex (hosted Exchange, etc).

If you're just looking to be able to send arbitrary SMTP to the Internet w/o running afoul of your ISP's deep-packet-inspection, you might be looking for something like the MailHop Outbound service from DynDNS.com. This service, as an example, lets you specify their SMTP servers as a "smart host" in your existing on-site mail server (letting you use a variety of destination port numbers, assuming your on-site SMTP server supports using non-standard port numbers) such that your existing on-site mail server delivers outbound email to the DynDNS.com servers, which in turn perform final delivery to the Internet.

As Richard West has pointed out in the comments, the Mailhop Outbound service, at its default pricing level, only allows 150 relays / day. You can purchase more relays / day as necessary, or you can look at other providers who might offer more relays / day or relays / dollar. Bandwidth isn't free, so you're going to find transfer limits of some type (bytes or relays per day, typically) with most providers.

There are a variety of providers out there that can provide this level of service. Be aware that none of them take too kindly to unsolicited commercial email, so be sure that you don't run afoul of their policies with what you're sending.

If you're just looking for the ability to do "mass mailings" you might be happier with one of the mass mailing services mentioned by other posters.

We use Constant Contact to do email blasting to our customers. It works wonderfully, has very detailed reports, and seems to be pretty inexpensive.

With that said, to avoid the problems you're having with your ISP, I would consider running your own mail server. Without knowing your company's IT infrastructure, I can't really make a good suggestion, but I'm partial to Microsoft Exchange. If you have a small business, look at running Small Business Server.