Although I still do not know the source of this error (essentially my exchange store stopped being able to mount) the fix was rather obvious. Searching the web did not help though. Microsoft said it was a problem in Exchange 2003 SP1 and Googling showed me many people who gave up and restored their last backup (which of course would be the best solution).

ESEUTIL by itself kept throwing the same JET_errFileIOBeyondEOF error except for eseutil /k "C:\Program Files\Exchsrvr\MDBDATA\priv.1.edb" This showed that my .edb data was fine but it stopped at the .stm file.

Microsoft(R) Exchange Server Database Utilities
Version 6.5
Copyright (C) Microsoft Corporation. All Rights Reserved.

Initiating CHECKSUM mode...
Database: C:\Program Files\Exchsrvr\MDBDATA\priv1.edb
Streaming File: C:\Program Files\Exchsrvr\MDBDATA\priv1.STM
Temp. Database: TEMPCHKSUM5352.EDB


File: C:\Program Files\Exchsrvr\MDBDATA\priv1.edb

Checksum Status (% complete)

0 10 20 30 40 50 60 70 80 90 100
|----|----|----|----|----|----|----|----|----|----|
...................................................


29186 pages seen
0 bad checksums
0 correctable checksums
316 uninitialized pages
0 wrong page numbers
0x42c067 highest dbtime (pgno 0xd4)

1825 reads performed
114 MB read
2 seconds taken
57 MB/second
1809651 milliseconds used
991 milliseconds per read
1516 milliseconds for the slowest read
63 milliseconds for the fastest read

File: C:\Program Files\Exchsrvr\MDBDATA\priv1.STM


So I simply deleted my .stm file and rebuilt it with C:\Program Files\Exchsrvr\bin>eseutil /p /createstm "C:\Program Files\Exchsrvr\MDBDATA\priv1.edb". Voila, it worked and I could mount my Exchange Store! CAUTION: there may be user information in this file. If your users are all Outlook clients it is probably not much used but if your users are IMAP/POP3 users then they may have a lot of information there which will be lost. Q555146. Always make a backup of any file that you are recreating.

Microsoft(R) Exchange Server Database Utilities
Version 6.5
Copyright (C) Microsoft Corporation. All Rights Reserved.

Initiating REPAIR mode...
Database: C:\Program Files\Exchsrvr\MDBDATA\priv1.edb
Streaming File: C:\Program Files\Exchsrvr\MDBDATA\priv1.STM
Temp. Database: TEMPREPAIR4596.EDB

Checking database integrity.

Scanning Status (% complete)

0 10 20 30 40 50 60 70 80 90 100
|----|----|----|----|----|----|----|----|----|----|
...................................................


Scanning the database.

Scanning Status (% complete)

0 10 20 30 40 50 60 70 80 90 100
|----|----|----|----|----|----|----|----|----|----|
...................................................


Repairing damaged tables.

Scanning Status (% complete)

0 10 20 30 40 50 60 70 80 90 100
|----|----|----|----|----|----|----|----|----|----|
.........................
Deleting unicode fixup table.
..........................


Repair completed. Database corruption has been repaired!

Note:
It is recommended that you immediately perform a full backup
of this database. If you restore a backup made before the
repair, the database will be rolled back to the state
it was in at the time of that backup.

Operation completed successfully with 595 (JET_wrnDatabaseRepaired, Database cor
ruption has been repaired) after 116.391 seconds.

Below are some additional links to Microsoft support write-ups.
Q313184
Q555146