Obviously this question is a little squishy, as YMMV, but I’ve run several WP sites using W3TC and similar plugins to yours on 32M, and haven’t had an issue.
That being said, when are you typically running into issues? Is it on post submission? On gallery operations? Looking for a pattern there could be helpful. Let us know if you find one.
Also remember that a limit is just that, a limit. The majority of the time your site will not be running at the max of 32 or 64M, especially with a caching plugin like W3TC installed and properly configured. PHP may burst to 64, but so long as your server can handle bursts up to that level, then you should feel comfortable with it. Generally, memory limits can be set a little higher than what you’d expect, and so long as you aren’t causing your server to thrash then you are fine. Try running top or free -m -s 5 to examine memory usage over time, and see if you’re constantly running close to the limit, or if it will continue fine as it is.