Just a word from a wise: That software is a rip-off. There's many softwares even not open source that cost just a tad less than that ($50-200) that does the same thing and comes from a real reputable company
With a VPS you have full root access so you can pretty much install any 3rd party applications you want as long as it is legal and not in violation of our TOS. Hope this helps.
Here's one very popular open source one: phplist.com
Since you were looking to pay $500+ for that contractor plus (piece of junk IMHO) here's an excellent piece of software by a very reputable company for $289: