This issue seems to be related to changed WordPress has made to their codebase since 3.0.1 (not sure which release but 3+)
The permalink structure for their tag posts used to be /tag/%tag% where %tag% was replaced with the post tag in question however for some reason they have changed this to /tag/%post_tag%/
Therefore as my plugin doesn't rely on core WP code to return formatted permalinks on version 3.1 this would have caused an issue.
Users need to know that my plugin has been designed totally differently from the others out there which are mainly based on loops through each data set (posts,pages,tags,categories etc) and for each record more function calls are made to get permalink structures and then the necessary related categories,tags,author names etc to parse the permalink with.
My plugin has taken a totally different tact and to try and increase performance, lower DB calls, reduce loops and memory usage etc it bypasses a lot of the standard wordpress functions and returns the data straight from the database (pushing the load from web to DB). This is why with other plugins the more records you output the more DB calls are made whereas with my plugin the no of DB calls remains the same >> read this plugin performance comparison.
Therefore when WP change things like the format of their core permalink structures (which shouldn't happen often) the code will need updating.
Some people may see this as a design issue other may not. If you don't like this way of doing things then there are plenty of other sitemap plugins out there that do things differently :)
By the way I am not complaining at the two posters above just making a general point to future readers in case they experience similar or future problems.
Anyway this was the cause of the issues to do with missing slashes and %post_tag% appearing in the sitemap.