I found that reindexing can help reduce these errors. If it doesn't, drop and create the index on the offending table(s). See if the offending tables have clustered indexes...

I too found that xp_sendmail failed from a scheduled job, worked when run interactviely. I connected to the server with terminal services (like being at the console), and recreated the...