VBA security is widely considered to be pretty poor. The VBA code isn't compiled, and the source is available in the excel file. The password protection is pretty easy to circumvent.
As I understand it, Office 2003 and earlier saves the vba code as part of the binary format of the worksheet (or document / presentation). When you fire up the VBA IDE, it simply looks to see whether the VBA code has been "protected" or not. This doesn't mean it's encrypted - just unavailable for viewing. The theory is that this stops your users from meddling with your code, but a hard-core coder would be able to get around the password.
Office 2007 does encrypt macros (don't ask me how or what algorithm). This is necessary presumably because XLSM files (or any Office 2007 file) are just zip files with a different extension. Anyone can get into those files and poke around.
To answer your last question - how does the password removal work on older Office formats, I'm not entirely sure. Different vendors will possibly approach the problem different ways, but I suspect the most common approach will be a brute-force attack on the passwords until a match is found.
The Excel VBProject object has a Protection property which will return different enumerations depending on the protection status of the macro (vbext_pp_locked if the macro is protected, for example). If you were to keep trying passwords programmatically until the vbext_pp_locked evaluated to false, you would have found your password.
I wonder if there is an option in 2007 to store only the byte code for macros within a workbook, allowing you to deliver functions without the source?
That functionality isn't (AFAIK) baked into any version of Office. Rather, the expectation is that if you specifically want automation for an Office file bundled, you'll use the Visual Studio Tools for Office (VSTO) to write your own DLL and store that as an add-in.
FYI - I created an xlsm (using the converter available for 2003). Changed the xlsm extension to xip, unzipped and looked inside. All the VBA was inside a single file 'vbaProject.bin'. In a hex editor it appeared to be build from exactly the same BIFF blocks that other excel files are made from. All strings in the macros were plainly visible. So it doesn't look as if the encryption has changed too much.
@DaveParillo - Huh. Thanks for that. I was led to believe that the code was encrypted. Should probably have checked for myself.