You can never have too much ram. Having said that, 256 will work fine, but as you noticed 512 meg works better. And if you increased to a gig you see another improvement, but not quite as signigicant as 256 to 512. Somewhere between those two numbers would be fine (though I'd prefer the higher).
You also want to make sure to take advantage of the paging file. There should only be one (on your fastest drive if you have more than one, or the largest partition if you only have one HD). And it should be set for 1.5x your installed ram - both maximum AND minimum to avoid fragmentation. In other words, with 256 meg ram you want min & max set for somewhere around 384 meg on one drive only.