I'm using the service "Nokia Email" which does delete from the actual source. I check the web yahoo interface regularly and for sure emails deleted from 2 weeks back were being redelivered by Nokia in one big transaction

Nokia is definitely keeping deleted emails....

The solution for Nokia is simple: each time email is down or BS re-deliveries.. fire(not demote) a manager if it happens twice under their watch (unless its a rare hard-ware failure where primary and backup goes down)