I understand your concern about Duman's behavior. It's no fun to find stool where it shouldn't be.
Cats stops using their litter box for a few reasons:
1) They don't feel well and associate pain with their litter box so go elsewhere hoping not to experience discomfort.
2) Their litter box is dirty, hard to get to or in or out of, they don't like the litter in the box, or they don't have enough privacy in it or feel trapped in the location it is in.
3) Other cats (can be indoors or outdoor strays), dogs or people are scaring them when they are in the box or trying to get to the box.
4) Social stress and overcrowding. Cats in the wild do not live together. It is socially stressful for them to have to be confined together. That is likely why many cats stop "marking territory once they are allowed to go outside. They are less "socially stressed" because they have more room and get more exercise.
First I recommend limiting access to the area that he is inappropriately using as a place to eliminate or making it uncomfortable to go there. You can place plastic matts with the nubby side up in the areas he has defecated inappropriately so they are uncomfortable to stand on and defecate. The longer this goes on the more it becomes a habit. Since this has been going on for 3 weeks and he has loose stools it is likely that we need to find and treat an underlying problem that started all this as well as retrain him.
I am glad he's had a physical examination. Were his anal glands were checked, and a stool sample checked to make sure that he doesn't have parasites or abnormal bacteria? Sometimes spinal arthritis that makes it painful for him to go or maintain his position, especially in a small litter box.
I agree that since he has had soft stools since this behavior began then he may have inflammatory bowel disease. We may need to try several diets before hitting on the right one, and he may need medication too. We often use a medication called metronidazole in these kitties. It is an antibiotic with anti-inflammatory properties too. It helps rebalance gut bacteria and reduce inflammation.
We need to address any medical problems to have hope of retraining him successfully.
You also need to make sure that the areas that he has picked to go have been cleaned with an enzymatic cleaner, like Nature's Miracle. Although it may smell fine to you their noses are much better than ours and as long as the odor is there he will be attracted to those spots.
Make sure his box(es) is/are spotlessly clean, scoop stools daily, change litter completely weekly and clean the box itself. If the litter box is older than a year get a new one. Many cats don't like odor and an old litter box stinks to them. It might be fine to pass urine there as that is quick but stool takes longer so they are more particular. I am glad you have 3 boxes but four would be ideal with 3 cats. I hope they are in different locations and where he cannot be bothered and they are easy to get to. Some cats like to urinate and defecate in different areas and are very sensitive to being interrupted. I know you have done some of these things already but sometimes you need to repeat them and I list them all to be complete.
Make sure he has privacy when he goes, yet also make sure the box is easy to get to and get in and out of. Many cats appreciate low sided boxes, especially as they age. Some cats also like a bigger box to pass stools in so they have plenty of room. The plastic very low sided storage containers that fit under the bed work very well.
If you are using scented litter I recommend plain clay litter or plain scoop litter. Most cats find scented litter objectionable.
To help ease social stress you can try using Feliway sprays or diffusors. These are synthetic pheromones which mimic those produced to mark areas as safe and many cats find them soothing. You can also use pheromone calming collars as well. See this link for some examples: http://www.amazon.com/Sentry-Behavior-Pheromone-Collar-Inches/dp/B0026JAKWG
If these measures aren't enough you can try a homeopathic calming oral medication called Bach's Rescue Remedy. See this link for further information: http://www.bachflower.com/Pets.htm
And you could discuss oral medications with your veterinarian for IBD as well such as fluoxetine or amitriptyline as calming agents to decrease his stress.
Finally if he feels better when allowed to go out you may wish to construct an outdoor cat pen so he can safely spend time outside. Here are some examples: https://www.google.com/search?q=outdoor+cat+enclosure&espv=2&biw=1433&bih=665&source=lnms&tbm=isch&sa=X&ved=0ahUKEwih_eCY9YzQAhWJyyYKHfUFBUsQ_AUIBygC
For now you may need to confine him with food, water and a litter box in smaller room both to be able to monitor his stools and keep him away from previous places he defecated inappropriately.
Best of luck with this fellow and please don't take his behavior the wrong way. It sounds like he is trusting you to get him some help.