I think we may need to back up a bit.
I added a couple of new phones a few months back and also set them up with embedded voice-mail.
Unfortunately, I didn't realize at the time that they were at the limits of their embedded voice-mail licensing so the voice-mail never worked for these users. They were able to setup greetings, etc, but voice-mail never picked up.
If the user was able to setup their greeting, then they are fully licensed for a voicemail box. The embedded system won't let you create more voicemail boxes than what your licensed for. Did you either call forward on no answer to the pilot of Voicemail or use Call Re-Routing Assignment to designate the 1st alternative as voicemail? Without either or these, unanswered calls won't go into voicemail.
The client purchased 30 new voice-mail licenses and I updated the 3300 to recognize the new licenses.
The license count did not increase as I expected it to.
What process did you use to do this? Within "License and Options Selection" did you press the "Change" button, and then sync via the "Retrieve License" button, with the AMC? If this fails, your system can't see the AMC on the net. You'd need to do an offline sync, and offline license increase. A reboot should not be needed when adding licenses.
I added a net new phone, user and voice-mail and the voice-mail licensing increased by 1 as I expected.
What form are you looking in when you see that when you use a voicemail box, it increased by 1? "License and Option Selection" will show you what your system is licensed for, and "System Capacity" will show you what your configured for, and how many of each you've used. System capacity will show the increase when you use a mailbox, but License and Options will only ever increase when you purchase additional ones.