SQL Enterprise Manager can accomplish this because it looks at two different things.
SQL Servers announce themselves on the network using a special broadcast. SEM asks the computer through a Win32 API what announcement has it seen from a particular service. Next SEM then looks in the registry for any Alias you've created.
The SQLDMO.Application.ListAvailableSQLServers tries to wrap this functionality but from what you describe it seems to fail when disconnected from the network.
One thing to see how screwed up SQLDMO is is to use the loopback adapter to make sure you have the network stack loaded. If ListAvailableSQLServers works then it will tell you that ListAvailableSQLServers just won't work when the network stack isn't loaded.
You can replicate the behavior of SEM by using the following calls which you might be able to call from a CLR language.
Look at the NetServerEnum API. This call is looking for any Servers on the local net that indicate they support SV_TYPE_SQLSERVER. Then you would need to look in the registry under HKLM\SOFTWARE\Microsoft\MSSQLServer\Client\ConnectTo
to see what aliases are registered.
PS. Another benefit of this approach is that it doesn't require SQLDMO to be installed.