Nick, it would help to include the version of ArcGIS Desktop, ArcGIS Server, the type of Enterprise Database (SQL or Oracle) and the version, and if when you right click on the SDE database to look at the properties, if it says it needs to be upgraded or if it is at the same version as the desktop.
Older versions (~9.2?) uses to have an option to have an sde-schema which worked as a main control point for additional databases. (The Multiple vs Single designation is like "Scale factors", it always seemed the opposite to me). Later versions (10.x) allowed each database to be a more, standalone table, without dependancy on thise SDE data
I'm sure Vince will have a more straight forward way of explaining this, but in the mean time, here are a few documents/thread that may help you determine what you have now
SDE/DBO Schema pros and cons?
ArcGIS Desktop Help 9.2 - ArcSDE for SQL Server dbo-schema geodatabases
ArcGIS Desktop Help 9.2 - Using multiple geodatabases within a DBMS
If I remember correctly, there was a command that allowed you to convert from the older version format to the newer format....or....
Are you using versioning, topology-rules, editing, replication, etc with the SDE database? Do you have ArcGIS Services feeding from the ArcSDE databases? If not, you can maybe just set up a new database, in the format/permissions that you would like, and copy the features to the new database...that is start out clean. Might be a bit manual, but may give you a fresh database without any remnants from the older version. This could be automated with python.