After struggling a bit with KML I finally managed to get a working map with all the geo-referenced photos linked to it. The biggest problem is that Google Maps servers will cache the KML overlay for an indefinite time and this behaviour is not documented anywhere.
Testing a KML generator is impossible until the trick is discovered. Just add a fake argument to the Maps XML API url, like this:

GeoXml("http://www.brownhat.org/photos/brownhat_photos.kml?100");

and then change it every time the KML changes. This way I discovered that Google Maps overlays are just bitmap tiles generated server-side and positioned over the map tiles.