My memory is a little foggy and we have upgraded to Sql 2008. But from what I remember I had to break the MP up into individual Databases and that solved our issue. Originally I had set the MP to do all our User databases. Everything worked OK and then I had a database that was removed from production so I went back into the MP and removed the database from there. But every time the MP ran it continued to look for the deleted DB. I decided it was easier to do a MP for each individual DB and from that point on I no longer saw the errors I had encountered before. Sorry I can't be of more help but as I said we upgraded our servers and I have not had any problems since I changed the Maintenance Plan...