i too agree the only surefire way to dramatically affect a deteriorated boot time is to reformat/reinstall. however, since many people customize their PCs, it's not always practical.
i've recently doubled my notebook's RAM to over 1Gb and it did nothing to my boot time whatsoever. it has however paid dividends in other ways.