Jason,
What version of Unity Connection do you have?
How are you adding the users? From the web page as standard users, through a Bulk tool or importing from AXL and LDAP?
When you say you have to add a notification device, you mean like send a SMTP notification, or a phone notification?
What you are describing is not nornal behavior.
When you say MWI doesn't work for new phones, if you call and leave them a messge (when they are broken), if you go to the "Message Waiting Indicators" page for that user, do you see a line there? Does it say On or Off for current status?