I highly recommend xanthan and guar:
https://forums.egullet.org/topic/138207-xanthan-gum-in-ice-cream/
If you can tolerate the polydextrose, I'd add more. I would try doubling it. Depending on how it's manufactured, polydextrose gravitates towards pretty high molecular weights, but scoopability is much more than just a freezing point depression game- air, as you noticed, is a big player, as is limiting water activity. Emulsification also plays a role. Polyd is a weak emulsifier but a very strong water activity inhibitor.
At the quantities you're using, I think there's a decent chance some of your erythritol is re-crystallizing, which would account for the strange cooling sensation you're experiencing. Dissolved erythritol doesn't give off that endothermic reaction, but keeping it dissolved can be difficult. I've tested a pretty wide range of polyd/e syrups, and, it seems like the version that's happiest/least prone to recrystallization is 3 parts Polyd/1 part e. If, say, you go with 2/3 C. polyd, I wouldn't go above a quarter cup erythritol.
With the drop in e, you'll lose some sweetness, but you weren't getting much sweetness to begin with, so, as you figured out, you'll need a high intensity sweetener. If you have a brand of stevia that you like, it might work well with vanilla, but, should you want to make chocolate ice cream, where the sweetener needs increase, stevia might not cut it. Erythritol has an exceptional synergy with splenda. By combining them, you can use exponentially less than on their own. I'm guessing that since you haven't mentioned splenda, you're not a big fan, but one advantage of using two sweeteners is that you'd be using very little splenda. Another high intensity sweetener with great synergy with erythritol and splenda is ace k. That's the best taste you're going to get. Ace K has a pretty questionable track record in terms of health, but, as a component in a formulation, you can get away with using microscopic amounts.
You might also consider xylitol. Birch xylitol is supposedly superior. It's a sugar alcohol, which carries all the side effects that sugar alcohols carry, but it seems to be a tiny bit more benign than most. The bottom line- the greater variety of sweeteners, the better. As far as I know, erythritol and xylitol don't have synergy with each other, but xylitol should have great synergy with polyd- and splenda and ace k. So with a little xylitol- perhaps a small enough amount that prevents digestive issues, you can dial the splenda and the ace k way way down. That way, if you have health concerns regarding splenda/ace k, you can somewhat mitigate them by knowing that you're ingesting them in incredibly small quantities. Or you can do polyd/e/xylitol/stevia, which will taste better than polyd/e/stevia. But, again, though, should you ever decide to work with chocolate, trace amounts of splenda and ace k will knock it out of the park.
The other advice I'd give you is to go with smaller batches. The faster ice cream freezes, the smaller the ice crystals. And, while I think whipping the cream is a worthwhile idea, be careful not to whip it too much, or the freezing process will make butter, and produce a greasy mouthfeel.
Lastly, polydextrose is polymerized dextrose, while inulin is polymerized fructose. Neither process produces 100% polymerization, so, with polyd, you're getting trace amounts of dextrose, and inulin has trace fructose. Fructose does some wacky things in ice cream, such as boost the sweetness far more than the quantity used. I know fructose has it's critics- deservedly so, but the trace fructose in inulin might be worth it, especially if you won't use artificial sweeteners.
edit: This is also a useful discussion relating to sf ice cream formulation
http://www.chowhound.com/post/purchased-guar-gum-thickening-agent-319926
