Thanks for the questionCustomer
The first thing to do is what you have already done, have your cat examined by your vet in case this is some sort of medical problem, consider urinary tract infections or causes of excessive drinking such as diabetes
disease, these can occur in older cats.
Then if this is not a medical problem then it must be a behavioural problem, truthfully this can be a difficult issue to resolve, you may well have tried some of my suggestions but here are the sum total of the ideas which I have given to my clients in the past, some of these have worked well.
1. When you clean up after where he has been use one of the odour eliminator type solutions you can get from the vet or pet store. These work as they have a biological action like a washing machine soap powder and digest organic matter. In fact a dilute solution of such a soap powder is a good thing to use as well. If you just use normal soap and water it will smell fine to you but to the cat it will still smell it afterwords, and if the place smells like a public toilet to a cat he may use it as such! Make sure you leave the cleaning agent to soak for a while.
2. Try moving the cat litterbox, that's often a good thing to do. Best advice is to keep the litter tray well away from food
or water bowls because that could be reason he does not go. Sometimes providing another litter tray elsewhere in the house is a good idea as well.
3. Change your cat litter to another brand which is very different in colour and texture from the brand you are using now. Also consider using earth from the garden instead of cat litter, it is not quite so absorbent as cat litter in terms of smells etc. but it is much more natural for the cat and might bring him back into his litter tray.
4. Some cats start to be dirty in the house because they are marking out their territory in response to some anxiety, another cat in the neighborhood etc. Products such as Feliway can help here, some of my clients swear by Feliway. It is used a lot in the UK but hopefully it is available in your area, your vet will advise. I have put a link about Feliway below. LINK
5. Some cats respond to low level tranquilisers where territorial anxiety concerning other cats is a factor but this is a last resort, it often works well though.
If I have not covered your question fully enough or you would like to ask more I will be online for the next hour or so and I will be at your disposal
Scott Nimmo BVMS MRCVS