This is now fixed. It has been 3 days now since the fix and the problem has not returned.
For the solution, we deleted the hunt group and recreated it. We also noticed an error in our call routing setup (we hadn't properly told it where to send no answer / busy calls). After doing both of those, everything is now fine.
We did first try the steps that you outlined, but it wasn't delivering the voicemail on no answers. That being said, before we got too deep in it to really figure out why, we recreated the hunt group since it had been deleted, and noticed an error we made previously in our routing for these phones (we weren't telling it where to go on no answer calls), and then the problem was resolved, so we were all set then anyway.
thanks!!