I used to use Fusion and Parallels and a well optimized WinXP on my RevC MBA w 2gb/128gb ssd.
If the use was light and XP was well optimized and you were not trying to run much else in OS X then Fusion ran well and Parallels ran very well. Parallels used to be a bit less stable than Vmware but much faster. Now I use Parallals almost all the time for its much higher speed and similar reliability.
If you tried to do to much else or needed Vista or W7 the experience was much poorer with 2gb, but I imagine 4gb would easily allow one optimized VM (any Win OS) along with your other routine OS X stuff.
My fairly routine use of VM's is what ultimately forced me back to a 13" MB. The MBA simply did not have the memory or storage capacity for my needs (although it was very fast and WONDERFUL to travel with).
With the release of the new MBA with a 256gb SSD and 4GB of RAM I might consider it again - this is definitely enough for all my OS X activities and one well optimized VM to run at the same time.
Hope this helps
