Exchange 2007 Mailbox inaccessible

Bit of an odd one this, I've come back after a week off and my Exchange mailbox is completely inaccessible. The rest of the staff (20 or so) are all fine, but I cant connect to mine using either:

1. My Phone
2. My iPad
3. Outlook 2007
4. OWA

So far I've tried:

1. Resetting my AD password
2. Checking permissions to the mailbox
3. Checking the relevant services are running

Outlook just keeps prompting me for a password (which is most definitely correct), OWA gives the following error message:

Exception type: Microsoft.Exchange.Data.Storage.ConnectionFailedTransientException
Exception message: Cannot open mailbox /o=DOMAIN/ou=first administrative 
group/cn=Recipients/cn=josephb.

Exception type: Microsoft.Mapi.MapiExceptionLogonFailed
Exception message: MapiExceptionLogonFailed: Unable to open message store. (hr=0x80040111, 
ec=1010) Diagnostic context: Lid: 18969 EcDoRpcExt2 called [length=456] Lid: 27161 EcDoRpcExt2 
returned [ec=0x0][length=124][latency=0] Lid: 23226 --- ROP Parse Start --- Lid: 27962 ROP: 
ropLogon [254] Lid: 17082 ROP Error: 0x3F2 Lid: 26937 Lid: 21921 StoreEc: 0x3F2 Lid: 27962 ROP: 
ropExtendedError [250] Lid: 1494 ---- Remote Context Beg ---- Lid: 26426 ROP: ropLogon [254] 
Lid: 4740 StoreEc: 0x80070005 Lid: 30409 StoreEc: 0x80070005 Lid: 19145 StoreEc: 0x3F2 Lid: 
23241 StoreEc: 0x3F2 Lid: 32186 Lid: 8620 StoreEc: 0x3F2 Lid: 1750 ---- Remote Context End ---- 
Lid: 26849 Lid: 21817 ROP Failure: 0x3F2 Lid: 26297 Lid: 16585 StoreEc: 0x3F2 Lid: 32441 Lid: 
1706 StoreEc: 0x3F2 Lid: 24761 Lid: 20665 StoreEc: 0x3F2 Lid: 25785 Lid: 29881 StoreEc: 0x3F2 

I've also tried the Test-ActiveSyncConnectivity cmdlet which gave me the following:

[System.Net.WebException]: The remote server returnedan error: (503) Server Unavailable.

HTTP response headers:

Content-Length: 0
Cache-Control: private
Date: Wed, 20 Jul2011 09:57:26 GMT
Server: Microsoft-IIS/7.0
X-AspNet-Version:2.0.50727
X-Powered-By: ASP.NET

I've been scouring the internet for about two hours now but can't seem to find a suggestion left that can be done during office hours. Any help would be greatly appreciated.

Have you checked for updates? Looks like there's a rollup for SP3 that describes at least one of the issues you're having. http://support.microsoft.com/kb/983296