I have never used a sitemap and have never had any issues with Google crawling and indexing my sites. How will adding the sitemap help?
how many pages is your site ? The only coincidence i noticed was g crawling my site @ 'nearly' the same time as mentioned in my sitemap. Mine is blog and g was crawling the old post once a week and home pages everyday as defined in sitemap. but must admit don't know if this was is the default behavior of g.
Sounds like they are useing site map like meta tags used to be used for. Site maps can also help get new pages indexed faster and old pages listed if not already.