If you’ve recently installed ArcGIS 9.3 Service Pack 1, be aware that there is a patch out that fixes an issue with topology validation. You can read more about it here:
http://support.esri.com/index.cfm?fa=knowledgebase.techarticles.articleShow&d=35833
This patch seems to apply to Desktop, Engine and Server so you may want to check it out.