Well, here's your answer in the USA....

http://www.mizpee.com/web/index.html
http://www.techcrunch.com/2007/06/27/when-youve-got-to-go-go-to-mizpeecom/

...You owe SearchEnginesWeb!

Nice & innovative service,
Actually a very important service too in times of emergency ;)

I'm sure people would use it

Who will have patience to find the location in mizpee to pee. ;-)

The Australian National Public Toilet Map:
http://www.toiletmap.gov.au/

You can even "Register to save your trips, favourite destinations and public toilets"!