So...
I've used the "Repair" method a couple of times now, and it's interesting what happens. I always have to click repair, then it it tries to do it and comes up with a login box for the account and I hit cancel. Then I restart outlook and hit repair again, this time it immediately works and says you have to restart outlook. When I restart outlook, the archive mailbox is there.
Now, this is where it gets interesting. The archive mailbox will usually disappear usually after about a minute, right in front of my eyes. I then repeat the process over again, and it may take a few times through and then it sticks (don't know how permanent it will be). It has taken 2 attempts up to about 5 attempts.
I just did this with a user and it was the longest number attempts, like around 5, and I decided I was going to capture the outlook profile out of the registry when it was working and not working, and so I did. I captured it when it was "broken", after I fixed it, and after an outlook restart when it was "Working". Aside from some small changes between the profiles, the biggest difference is that on the fixed and working captures there is an entire extra key under the profile which contains the mapping to the archive guid. Unfortunately this key is a random number, so it's not the same between profiles.
So basically it seems that whenever this issue happens it deletes this registry key from the outlook profile in the registry and is then no longer opening the archive mailbox.
Anybody have any ideas as to what may be causing this?