Maintenance plan to delete backup and restore history not working
In the Maintenance plan job, create an output file to see what exactly is going on during the job run. Mostly there is something missing.
Drop and recreate the plan and test.