"What are you?
Columbo, with the third degree?"
We've covered Columbo's fame in Toobworld before. We've even posted about 'Columbo' in connection to 'The Mentalist' as well.
I think Red John would have kept himself up to date on the rumpled detective's status there in California, right up until the day Columbo passed away. (Which was not long after the death of an actor who looked very much like the Lieutenant, Peter Falk.)
If anything, Red John appreciated the possibility of a worthy opponent and he would have made certain that his identity was safe from Columbo's notice.