Hi Paul,
Check document
http://seer.entsupport.symantec.com/docs/335411.htm
Could that be the issue?
Additionally, you might want to try examining this account using ADSIEdit to see what it states in there.
Could it be replication for the AD not working properly?
When you ran provisioning, did you sync the mailbox after that? Try that also.
Also check forum entry https://www-secure.symantec.com/connect/forums/error-enabling-mailbox
That is almost the same, and has some sql-queries to run to verify
And also https://www-secure.symantec.com/connect/forums/cant-find-user-vault-enable-their-mailbox might help
Good luck.
Regards. Gertjan