SQL Server Backup Job Maintenance Plan - Problem with Proxy Account and Permissions

I created a SQL Server Maintenance plan to backup all our databases and store the files on a share. The job owner is "SA" but the job step is set to "run as" a proxy account. The proxy account's credential is a domain account that has the following database rights to MSDB - db_backuperator, db_dtsoperator, SQLAgentUserRole.
Now we obviously don't want to give the credential/domain account SysAdmin rights to the server (which BTW, allows this job to run without a hitch). We just want to give the bare minimum, as per best practice. So when we run the maintenance plan, the job fails and we get the following error message:
Message
Executed as user: XYZsqlbackupadmin. ...9.00.5000.00 for 32-bit Copyright (C) Microsoft Corp 1984-2005. All rights reserved. Started: 6:00:00 PM Error: 2011-03-31 18:00:11.60 Code: 0xC002F210 Source: {2012CDE4-7671-40B1-92F2-26A84187DCDA} Execute SQL Task Description: Executing the query "DECLARE @Guid UNIQUEIDENTIFIER EXECUTE msdb..sp_maintplan_open_logentry '{1025AEF1-AC7C-48FB-9D44-C595BAF4CEBC}', '{845EB87D-0CB6-4E83-BFBD-298EA1B60FBD}',NULL, @Guid OUTPUT Select CONVERT(nvarchar(38),@Guid) AS RunId" failed with the following error: "The EXECUTE permission was denied on the object 'sp_maintplan_open_logentry', database 'msdb', schema 'dbo'.". Possible failure reasons: Problems with the query, "ResultSet" property not set correctly, parameters not set correctly, or connection not established correctly. End Error Error: 2011-03-31 18:00:11.72 Code: 0xC0024104 Source: {E8DD7625-07DD-48C0-A98F-DE163EAE8A61} Descript... The package execution fa... The step failed.
I've tried a variety of things like making the domain account (credential) db_owner for MSDB without any success. Again, the only thing that seems to work is if I give the domain account (credential) SysAdmin rights which won't cut it for us. Please advise. I'm at the end of my rope with this...
Thanks in advance to all who reply!

Hi satya and thanks for replying. I gave the proxy account 'db_backupoperator' rights in the msdb database which also gives the proxy account 'db_backupoperator' rights to all the other databases in the instance. Still no luck. Thanks again!

Hi satya - OK, I think I found an easy way out of this. I'm keeping the maintenance plan to do the cleanup in the beginning of old backup files. But I removed the part that actually creates the backups. I then add another step in the job (in SQL agent) and run this backup script which I found here:
http://www.mssqltips.com/tip.asp?tip=1070
I have the script run as the domain account which we created to perform backup jobs. Seems to be working OK (so far). Thanks for all your assistance!

Hi, I wonder, if you save maintenance plan, does it change "run as" proxy account? Becase everytime I save maintenance plan it changes all steps "run as" in all jobs, which were created by maintenance plan, back into SQL Server Agent Service Account. If I save it I must change all jobs back. Look at it pls. The owner of maintenance plan is dbdb_backupoperator account. should it be SA? This happens in SQL 2005, 2008 2008 R2.
thanx
Jiri