A Google Maps Help thread has confirmed reports that searching for user generated content via My Maps seems to no longer be returning results.
ehg, a helpful Google Maps forum member helped debug this. He said, all of my maps of MyMaps created until 20 Oct 2009 are still to search. Here a sample map "GRZG" which is still to search  when searching "related maps" and "GRZG". Here searching for a user- created content ("ghghgh5656") of the same map  I created the map 10 Oct 2009. And here a search for the last map I can search & find (created 20 Oct 2009 - the second map is a copy of the first one I created at this date) .
Googler, Brian B, said, "I'm looking into this and will give an update here. Thanks for escalating."
Forum discussion at Google Maps Help.