Post Office was the first sign of the error.
When I run a GWCheck on the User
I get
 Checking user = rca (lzs / 199) 671109120 bytes, 04/14/11 06:01 (Raoul Carmody [IT/AV Services])
  - Current time 9:41:2 am
    STRUCTURAL VERIFICATION of database MAIL01/GWDATA:\staffpo\ofuser\userlzs.db
      Verifying data
    - structural problem detected- COULD_NOT_SYNC_BLK (code 0x67)
          - Additional info saved in MAIL01/GWDATA:\staffpo\ofuser\userlzs.$er
          Problem 13- Structural problem found in database MAIL01/GWDATA:\staffpo\ofuser\userlzs.db
          - Attempting to correct structural problem in database
      - Beginning rebuild for database userlzs.db
          Error 26- DbRebuild error IO_FILE_LOCK_ERR (0x820E)
The additional info is
  Logical File Number: 1546
  Logical File Type: Domain
  Level in B-Tree: 0
  Block Address: 671109120
  Parent Block Address: 671022080
  Error Number: 67
My thinking at the moment is to take the post office offline after hours and do an offline gwcheck (Structure, Contents, Fix) on the user. Data Synchronizer and/or Groupwise Mobile I think is locking his database.

Oh and it's Groupwise 8.0.2 running on a NSS volume on a Netware 6.5sp8 box.