As mentioned here, I released a patch for making the xmlsitemap module work under Drupal 6. It's still in the code needs work mode, but I'm getting there. So any developer who wants to help, go for it.
It shouldn't be that much work that finish it.
Update: I think the major part of the work is done. For me everything seems to work now.
You can see the result here: http://www.denraf.be/sitemap.xml
You can download the patch here: http://www.denraf.be/files/drupal6_5.patch