Tom,
Thank you for providing the test data. ArcGIS 9.3 does have a bug in Dissolve, not doing UNSPLIT correctly. I can't think of an easy workaround. Sorry about the problem you run into.
I have tested in ArcGIS 10 SP3 and Dissolve seems to work correctly; I didn't verify every resulting feature, but a few that didn't work in 9.3. Many features remain unchanged even they have common feature code because they are not connected.
If you can find a colleague who has ArcGIS 10 and can run the process for you, that would be great. Otherwise, I hope you would upgrade to ArcGIS 10 in the near future.