Tanza, if I am not mistaken, you posted a wonderfully handy description of basenjis, including their good traits and not so good traits. Please post it again for new owners. Prospective buyers: a reliable breeder will tell you all about a basenji, the good and the not so good. Don't buy from someone who has only good things to say. This HONEST advice would apply to any purebred dogs.
I have owned three basenjis, two tris and one b/w, all born in Sweden, where we lived for many years. I wish I'd had your list back then for our first B but we finally "worked things out" with him. I have another dog now, a rescue Sheltie, and I love him dearly but I do miss all the things that make Bs so special. My first two lived to be 15.5; the last one was 16.5 she passed away. Wonderful years with all three.
What was his living situation before you adopted him? It's never too late with a basenji. They are very smart and can learn new behavior. It may take time but it will be worth it. Perhaps it is time to hire a professional dog trainer who could give you some advice on how to deal with this problem. Often it is a matter of how one reacts to the dog's misbehavior. You are doing everything that you can, and it is not working. i agree about the long walks and distracting him any way you are able. Never get angry at a dog! Even if you are furious. Basenjis especially are very smart but also sensitive. Unless there is something wrong with him physically, you should be able to get him to behave eventually.
btw, has he been neutered? Do persevere. You'll be glad you did.
Hi, all three of my basenjis were fine in the baggage compartment but I have a Sheltie now who, because of the six years he spent in a puppy mill, would not be a candidate for the baggage compartment. How about going the "emotional support animal" route? I suggest you google that. You have to "guarantee" that your dog is well-behaved, etc, and there's paperwork but it is very possible that you could make that work for Toby, who is a beautiful dog, btw.
I've never known a basenji to be kept outside. They are family dogs; they like to be with people. I've lived with three basenjis and knew countless basenji owners in Stockholm, where we lived for 12 years. None of the owners kept their dogs outside. It's people they want to be with; they want the warmth of people, not a dog house. Sorry to sound so harsh. Basenjis are very special dogs, and it would serve prospective owners well to learn as much as they can about the breed before they acquire one. The fenced-in yard sounds good.