I am reluctant to even mention this suggestion because it is loaded, but our Ella was only briefly and unhappily crate trained and we just made the leap (over several days) of leaving her alone and free in the house. While her record has not been perfect, overall the change has been a huge improvement. She would rarely relax inside her crate but now that she has freedom inside the house I am pretty certain she spends 90% of her time alone curled up on her bed asleep. That is pretty much how I find her twice a day. We thought the problem was separation anxiety but it was crate anxiety. So we removed the crate. I am sure we will have regrets in the future that Ella cannot be easily placed in a crate, but on a daily basis I think it may be worth a try.
My experience with Ella is that her destructive behavior occurs when WE ARE HOME and not paying enough attention to her. When she is alone she rarely causes trouble. My friend's Basenjis are the same way and are also not crated. She is the one that gave us the inspiration that a Basenji could be trusted. Of course, we do our best to basenji-proof the house before we leave to take care of known trouble spots. And no "goodbyes" and explanations of comfort and concern. Just walk out the door as simply as possible.
I know this is the Basenji forum and not the Labrador forum but somebody had to suggest letting the dog free in the house.