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.
So Excel doesn't need to unencrypt any code - it just needs to stop people from viewing it.
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.