My client has a 40,000 strong document library. However this has become a
mess and it's his wish to effectivly de-commission the system. Thus I
need to export/checkout the 40,000 documents into some form of file
structure. Ideally with sorting options for creator/name/date etc...
keeping the DMS attributes.

Is there such a utility?

Or another option maybe it to transfer the DMS to a Groupwise 6.5.5
Windows 2003 server, and sort it out somehow?