If you're using Entourage 2001, increase memory to the application. Select
the application icon, and then go to File -> Get Info -> Memory. Set the
Preferred size to 25000K, then close the window.
If that doesn't help, try moving the preferences files to the Desktop (OS
9):
HD:System Folder

references:Internet Preferences
HD:System Folder

references:Microsoft:Entourage Preferences
If that doesn't help, try moving the preferences files to the Desktop (OS
X):
~/Library/Preferences/com.apple.internetconfig.plist
~/Library/Preferences/com.microsoft.Entourage.plist
~/Library/Preferences/Microsoft/Entourage Preferences
~/Library/Preferences/Microsoft/Entourage Settings (10)
Rebuild the database again if you still have problems. Try an advanced
rebuild and see if that makes a difference.