When exporting messages with attachments to a PST, Search Exporter will fail randomly on any attachment but when you view the link, the attachment is present and can be saved locally on the machine.
When you examine the SearchExport.EXE.LOG, it may contain errors similar to below:
2011-11-12 10:21:45,454 [6] INFO AfterMail.Log.MailExporter.PSTWriter - Created folder: ArchiveManager
2011-11-12 10:21:45,654 [6] TRACE AfterMail.Log.MailExporter.PSTWriter - Save MAPI attachment f54a8c43-b623-6217-8a22-8db733a54214
System.IO.FileNotFoundException: Could not find file 'C:\Users\testuser\AppData\Temp\Aftermail\7833\f1ab8395-3f43-a480-860b-05833e778784\f54a8c43-b623-6217-8a22-8db733a54214.xls'.
File name: 'C:\Users\testuser\AppData\Temp\Aftermail\7833\f1ab8395-3f43-a480-860b-05833e778784\f54a8c43-b623-6217-8a22-8db733a54214.xls'
at System.IO.__Error.WinIOError(Int32 errorCode, String maybeFullPath)
This is due to antivirus software installed.
Uninstall the antivirus software or disable and exclude the temporary path of the Windows profile used.