Disability and alternative to shoe removal?

I am planning to visit Japan but have come upon a problem. I have an artificial right leg. I cannot easily remove the shoe (this would require taking off the leg first) and anyway the foot on the artificial leg is designed to be used with a shoe on and would not be stable to walk on. I have now been told by the tour operator that if I cannot remove the shoe I will be unable to enter various sites (temples and some special events) and will have to stay outside. I have suggested that I could wear put in some covering over my shoes (overshoes? large slippers?) but they haven't even responded to this. They simply go on about local customs. I may need to cancel the trip which would be a great disappointment. Surely the locals will be more sympathetic of I make the effort to cover my shoes?

Sadly, the problem is not only related to the shoe being dirty. The tatami would easily be damaged if walking on them with a shoe, no matter how clean. So even wrapping it in a plastic bag or something would not be a good solution.
As a travel agent I know all too well that when dealing with traditional establishments, no matter how many times you try to find a compromise, if it is against the rules there will be no flexibility or sympathy at all.
One thing i can suggest would be to bring a soft slipper that will suit your shoe-ed foot with you, and put it over your shoe. If anyone tells you anything you can explain the situation. They could me more lenient in person when seeing the situation than when someone explains it to them beforehand.

Additionally you may try contacting the awesome folks at Accessible Japan https://www.accessible-japan.com/ they mostly deal with wheelchair travelling but they host a wealth of info in general about accessibility in Japan.

However, just because you might be unable to visit the inside of a temple or two it doesn't mean you have to cancel the entire trip. There is so much to do and see that does not require taking shoes off!

Some places offer slippers you can use but they are unlikely to fit over your artificial foot (They barely fit my size 45, UK 10 feet). The idea of bringing your own slipper is a good one. Probably the less it looks like an outdoor shoe the better. A laminated card explaining the situation in Japanese would help a lot. Unfortunately As @Guest says you can do a great trip without needing to take your shoes off.

There may be more problems than shoe removal that you tour operator has not told you about. Do you use crutches, cane, or wheelchair? Even if shoe covers are allowed, they may also ask you to put covers on crutches, which can make them slippery. Are you able to climb steep and narrow staircase or do you need an elevator? Do you have a dedicated assistant traveling with you? The tour operator may not even know where all the elevators are, and may be concerned that keeping a regular schedule for the group. I look for accessibility issues whenever I travel to Japan, because one of my best friends has an artificial leg and uses crutches. Based on my personal observations, I concluded that the best way for my friend to visit Japan is by putting him on a wheelchair, and have a tour guide/assistant (that could be me) with him.

I'm surprised that people are talking like this. But then, I'm surprised to realize that there is no obvious information about what Japanese Paralympic athletes are doing when visiting tatami establishments.

That said, (like any human being) I have relatives who use canes or cannot bend their knees, and they enter temple tatami rooms for granted when they attend family memorials. The temples keep (many) chairs at the edge of tatami rooms for the elderly and challenged to sit by us who are sitting on the floor. And our relatives would use canes with round edges to walk on tatami. Temples care for the dead, and the dead are close to the elderly. You can't help it.

I also notice that people with casts wear something over the cast when going indoors. Something as strong and waterproof as wetsuit material might be an option.

In any case, there are so many locals with artificial legs. I'm tempted to ask the boy who I often see on my bus to find out how he's managing it. Accessible Japan came to my mind to. Do ask them, and don't let people blame it on "local customs". But to be fair, I think travel agents need to "warn" you that things can be different. They're not exactly saying that you "will" have problems but only that it's a possibility.