It should be possible...
The PC3200 (DDR400) ram in my new machine has 3 sets of timings in SPD
1. @ 200 MHz 3.0-3-3-8 (CL-RCD-RP-RAS)
2. @ 166 MHz 2.5-3-3-7 (CL-RCD-RP-RAS)
3. @ 133 MHz 2.0-2-2-6 (CL-RCD-RP-RAS)
I was rather disappointed to see the extremely bog-standard CAS 3 ram in this machine (Medion MD8386 from Aldi), as for my "couldn't build it for the price" comparison, I'd actually picked RAM that was considerably better.
However, at 133 MHz (266FSB) this same RAM offers extremely tight timings - I don't think you'd better them, even with super-deluxe heatsinked special RAM.
If the RAM does not have an automatic SPD timing for 133 (266), then you'd have to set the timings manually.
One thing, if the old RAM is CAS3 and poor timings, and the new is capable of these really tight timings, there might be a small touch of extra perfomance in removing the old 256 and fitting a new 512 - if the motherboard can take 512's