(I encourage others with more historical knowledge to correct anything that may be inaccurate herein.)
The sad truth is you are not going to get the acceleration you want (not under Windows, anyway) without modern, massively parallel GPU technology (in the form of pixel shaders specifically). The last high speed frame-buffer rendering under Microsoft OSes, prior to the advent of consumer-level GPUs, was seen with the demise of the VGA high performance modes such as Mode X and Mode 13h under DOS, modes which allowed the rapid rendering of all high-end PC games in the early-to-mid 90's (Doom, Magic Carpet, Dungeon Keeper, the C&C games and so on ad nauseum). It was the innovative memory-access models in these modes that benefited non-parallelised performance; the low resolutions and consequently comparatively low iteration also certainly contributed (as compared with today high resolutions and highly parallelised GPUs developed to deal with this). Because these modes are no longer supported under Windows, you simply won't get the same sort of performance in the same way as those old games did.
There are some high performance (and not exactly cheap) solutions such as Pixomatic, which may interest you. I am not sure how they are constructed, given that eg. Pixomatic runs under Windows, but I can guarantee you they are highly specialist solutions that are built using extensive knowledge of old school VGA rendering, and more generally the subtle ins and outs of x86 architecture.
In conclusion -- You really should be writing a special-purpose pixel shader, unless is there some very good reason not to do so.