Безопасность VBA считается довольно плохой. Код VBA не скомпилирован, а исходный код доступен в файле Excel. Защиту паролем довольно легко обойти.
Насколько я понимаю, Office 2003 и более ранние версии сохраняют код vba как часть двоичного формата рабочего листа (или документа / презентации). Когда вы запускаете VBA IDE, он просто смотрит, был ли код VBA "защищен" или нет. Это не значит, что он зашифрован - просто недоступен для просмотра. Теория заключается в том, что это мешает вашим пользователям вмешиваться в ваш код, но хардкорный кодер сможет обойти пароль.
Так что Excel не нужно расшифровывать какой-либо код - ему просто нужно помешать людям просматривать его.
Office 2007 выполняет шифрование макросов (не спрашивайте меня, как или по какому алгоритму). Это необходимо, предположительно, потому что файлы XLSM (или любой файл Office 2007) являются просто файлами zip с другим расширением. Любой может получить доступ к этим файлам и копаться.
Чтобы ответить на ваш последний вопрос - как работает удаление пароля в старых форматах Office, я не совсем уверен. Различные поставщики могут подходить к решению проблемы по-разному, но я подозреваю, что наиболее распространенным подходом будет атака методом перебора паролей, пока не будет найдено совпадение.
Объект Excel VBProject имеет свойство Protection, которое будет возвращать различные перечисления в зависимости от состояния защиты макроса (например, vbext_pp_locked, если макрос защищен). Если бы вы продолжали пробовать пароли программно до тех пор, пока vbext_pp_locked не оценивается как ложное, вы бы нашли свой пароль.