VPS For Wordpress - PHP Memory Limit

If I have a two sites that, combined, get about 125,000 page views monthly (that comes out to about 4,000 page views daily). The sites are powered by Wordpress, and it is being used as a CMS, it's not a blog. There are a number of plug-ins in use, on each site, about 10 or so. Each site also has a vBulletin forum in use, although there are rarely more than 10 concurrent connections, if even that many (total of 400 members, only 150 of which are active -- combined stats for both sites).

Currently the PHP memory limit is set to 16M. I'm wondering how high it could or SHOULD go? Granted, I would not want to ask for more than what is available. Would the site speed improve if it was upped to say 128M? Let's pretend that I have a 512MB VPS SLM (no burst). It would have Linux+Apache+Plesk.

Is that enough of a VPS? Would I need to go to 640MB, 768MB, or even 1GB of RAM? Budget is an issue, so "yeah sure, go larger" is not an easy decision. It's also stupid to buy what's not actually needed. Maybe 256MB-384MB would be good enough?

Now then, what if I wanted to use this on a Windows IIS6 system instead? Let's say that I decided to add an ASP.NET wiki or blog to one of the sites. Clearly, that would demand more RAM, and I think Windows itself likes to eat more RAM. The Windows box would also have either Plesk 8.6 or Plesk 9. What's the difference in base RAM use that should be accounted for?

Virtuozzo is desired for either solution, be it Linux or Windows.
My current situation is shared, Windows 2003 Plesk, for these particular sites, and these two specific sites are loading really slow sometimes. Other times I get partial loads, error 500, or pure "unavailable" issues. Other sites, same machine, just fine.

Even the vBulletin forums on the same domains load okay and fast, but the Wordpress sites crawl. It is IIS6, so use of WP-Cache/etc is pretty much impossible. I tried another cache, and it works -- but only for maybe 2 hours at a time, then something happens to it, and the cache quits. It's enabled, but it just stops functioning properly.

My shortlist of the moment includes KickassVPS, FutureHosting, and EuroVPS, for whatever new VPS plan that needs to be gotten. I've been watching the VPS offers threads for the past two weeks. I'm leaning hard to FutureHosting, for this one project, because of the Seattle NOC, since one of the site admins is close geographically, and he always has trouble with the current site's location (other side of the globe, for him).

I'm hoping some of the WHT experts have some good answers for this. I've been researching this for a while, both on WHT and off, but I can't seem to get a clear answer from reading alone.