Failed backups, but really its cleanup that is failing, also random backups selected for deletion

Using ABR 11 17440, every day i get emails about some backups failing. I go to investigate and find that the "backing up" task has completed successfully, and i can access the current backup. The "backup failed" message comes from errors about failing to find the backup (which it must have if it is correctly appending the incrementals to the backup series) when "cleaning up/replicating" (there is no replication on this job).
It looks like when the task runs for this machine, it then tries to run retention rules for all machines in this task and fails at some point. (but the machine.local in question ran its backup successfully).

The retention rules seem really messed up anyways, as when i look at the archives, there are backups marked for deletion both out of order and also that should not be deleted yet (i.e. full from last week marked for deletion when retention rules specify keep 3 months worth)

Anyone gotten through this issue? This has been going on for ages, and i remember some similar posts here in the forum from before the "final" build of ABR 11 (btw, isn't there supposed to be one more build release of 11 after 17440? that was said by a moderator in this forum...)

Also, I have another backup task that when it is "cleaing up" recently has been taking 10+ hours (before i have to cancel it ). This task has 1 computer in it, which is a simple always full plan. something is definitely wrong here.

[...]
4 Information 11/6/2012 3:08:09 AM Command 'Backing up' has completed successfully.
5 Information 11/6/2012 3:09:16 AM Command 'Replicating backups/cleaning up archives (1st location)' is running.
6 Information 11/6/2012 3:19:35 AM Backup deletion has started.
7 Information 11/6/2012 3:19:35 AM Backup deletion has successfully completed.

[...]
24 Information 11/6/2012 3:19:42 AM Backup deletion has started.
25 Information 11/6/2012 3:19:42 AM Backup deletion has successfully completed.
26 Error 11/6/2012 3:19:43 AM Command 'Replicating backups/cleaning up archives (1st location)' has failed.
Additional info:
--------------------
Error code: 61
Module: 309
LineInfo: 4a8728dc8a1c94f4
Fields: $module : service_process_vs
Message: Command 'Replicating backups/cleaning up archives (1st location)' has failed.
--------------------
Error code: 507
Module: 64
LineInfo: a1d3981537c6874e
Fields: IsReturnCode : 1, $module : disk_bundle_vs
Message: Failed to open the backup archive by the ID.
--------------------
Error code: 507
Module: 64
LineInfo: a1d3981537c6874e
Fields: id : machine.local_Archive(1)_2012_09_23_03_01_50_766F35.TIB, $module : disk_bundle_vs
Message: Failed to open the backup archive by the ID.
--------------------
Error code: 1
Module: 64
LineInfo: 98130db273d2480
Fields: $module : disk_bundle_vs
Message: The archive is invalid or its type is unsupported.
--------------------
Error code: 9
Module: 64
LineInfo: 95962d9a14426d2d
Fields: $module : disk_bundle_vs
Message: Failed to find the backup.
--------------------
Error code: 9
Module: 64
LineInfo: 95962d9a14426d2d
Fields: $module : disk_bundle_vs
Message: Failed to find the backup.