I can think of a few potential causes for this. If you had recently changed the URL of the user archive access service without running a copyback is one. Another is a bug with non-latin characters in the email subject, which should be fixed in ESA version 2.
In Exchange 2003, unlike 2007, messages are copied up to the OWA cache first, so this process could be failing as well. We'd probably need a copy of the latest Archive Service log for starters to work out what the problem could be if the failure to upload to the OWA Cache is to blame.