Talk about good timing... Yesterday I post a list of fixes for Exchange 5.5 and I mentioned that the May 2004 roll-up fix for the Information Store was pulled because of a regression. Last night we posted the new build up externally so that you don't need to call us to get it. This replaces build 5.5.2658.04 with 5.5.2658.25.
You can download it here: http://support.microsoft.com/Default.aspx?kbid=841765
Why do you want to install this fix if you are still on the old version? The regression could cause Store crashes.