I would agree with the vet visit (or maybe even a phone call to your vet) just to be certain. Is there a pattern to where he is peeing or when he does it? Male cats can get stones that play hell with their kidney/bladder function. I believe it's related to diet but not sure on that point.
If he pees outside the litter box sometimes it helps to mop up a bit of the fresh urine with a bit of toiletpaper and then put that right in the litter box to transfer his own smell to the appropriate place. Make sure where he peed inappropriately it's extremely well cleaned up so as little scent remains as possible to call him back there as a potty spot.
Hope all is well with your kitty.
~~Jo~~