The sde connection information is indeed embedded inside the mxd and does not go to a .sde file to get the connection information. This setup causes problems when you want to upgrade a database from say Oracle 10g to Oracle 11g where all the SDE connections need to be updated to reflect the updated Oracle Client information. The same scenario would apply when you would want to connect to a different database.
My organization was hoping ESRI could change this methodology so the sde connection information could be sourced directly from the .sde connection file or use an environmental variable (Windows OS) to retrieve this information so it is not embedded, conceivably many times, in an mxd file. This would make database upgrades far easier where you would only need to make changes to .sde files or environmental variables on individual computers instead of multiple times inside many mxd files.