Otherwise, The problem is usually related to the recent history folder of windows.
It must be a bug of some kind because the problem appears on different machines with
different hardware but all with Office XP and Windows XP (with default settings). It appears even on my fresh install. Symptoms are slightly different on different computers.

And here are two solutions:
1) Temporary solution: Delete all files in this folder.
C:\Documents and Settings\(Your User Name goes Here)\Application
Data\Microsoft\Office\Recent.

2) Permanent solution: Disable the recent history.
Backup your registry first.
Open your registry and find this key.
[HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Policies\Explorer]

Create a new DWORD value, or modify the existing value called 'NoRecentDocsHistory'
set the value to equal '1' to enable the restriction.
Exit your registry, you may need to restart for the changes to take effect.
 

Registry Settings
User Key:
[HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Policies\Explorer]

System Key:
[HKEY_LOCAL_MACHINE\Software\Microsoft\Windows\CurrentVersion\Policies\Explorer]
Value Name: NoRecentDocsHistory
Data Type: REG_DWORD (DWORD Value)
Value Data: (0 = disable restriction, 1 = enable restriction)

Try step #1
If that helps just do the modifications above (step #2) for a permanent solution.

Note that emptying that directory doesn't affect the recent files that appear in the 'File' menu of the XP apps. It does affect the 'My Recent Documents' that appear when you click on the 'My Places' bar within the file-open dialog.

Also note that there may be files up to a year old in that directory, which doesn't fit my definition of 'recent'

This appears to be a known issue by Microsoft:
An Office program is slow, hangs or may appear to stop responding when you open a file from a network location
http://support.microsoft.com/kb/833041
http://support.microsoft.com/kb/313937