I am currently running my pfsense on a OLD P3 800mhz, with 512MB ram.. Have no issues with it at all, I vpn INTO it pretty much every day from work.
Now if your trying to setup a site to site sort of vpn, for say news or p2p download, etc. Then yeah that might be a bit much, buddy on another board just set that up with the giganews vpn and he has a fairly new box dual cpu 1.8GHz I think and when he downloads through the the vpn his cpu was at 50%, etc. And that was at the 50Mbit connection, so I doubt a old p3 could really handle that sort of vpn. But as road warrior server into your network it works great!
I keep meaning to update the box to something somewhat current, but hey it keeps ticking!