Kristyn - with all the things you have and are trying - maybe it is time to talk to the vet about checking him for a urinary problem, and if there is none - the possibility of using a medication for him. There is a variety of prescription medications that can help. Some of them are Prozac, Amitriptyline, Cyproheptadine and others. A few over the counter remedies include Feliway and Rescue Remedy.
You might try clicking SEARCH at top right of the forum and then enter "spraying" and Cat General - to find previous discussions we have had here. Good luck!