How can I unlock the boot loader on a HTC Magic?
The process for getting CM on HTCs in my experience (HTC Sensation, Raider, One S, Desire Z) has been to:


Unlock the bootloader, usually via HTC Dev, after installing only Sync Drivers
Flash Custom Recovery - TWRP preferred, but CWM works fine
Flash Superuser zip file for easy root. If that doesn't work, I can suggest VRoot, worked great on an Lenovo Ascend G610 with little documentation on the web
Run S-OFF tool of choice, sometimes terminal based, sometimes it's an easy apk
Set SuperCID for easy flashing of other stock roms
Flash Cyanogen and Gapps, make sure to clear data before first boot


Don't try to install custom bootloaders with S-ON, as I've bricked an HTC Hero that was S-ON, tried to flash Amarulz HBoot, and it never started up again.

The method above has successfully unlocked all the HTC devices first mentioned, without any bricks.

To answer your questions, you can't flash a custom recovery because you are S-ON. Perhaps you cannot get the unlock key for your HBoot because it predates HTCs unlocking program. My HTC Hero got an Hboot update that required the use of using HTCDev to unlock.

If you're looking to flash a recovery via ADB Shell, you'll need to use 'dd' for that.