Ok, htaccess should work then. Check if it's called .htaccess, so that starts with a dot. Also check if the .htaccess inside vbseo_sitemap/data is present. This is a different one, which just says "deny from all".
The .htaccess from the vbseo_sitemap-2-5.zip, inside the htaccess directory, should be located at
http://#####.co.nz/.htaccess - if you would try to load it from your browser it should say Forbidden. If it says "The page cannot be found" then it's not in the right place. Also check if
http://#####.co.nz/vbseo_sitemap/data/.htaccess is present.
There might also be the possibility that your host doesn't let you use .htaccess files. In that case there is little you can do. You can test this with these steps:
http://www.webune.com/forums/how-to-...abled-t40.html