My WP sitemap contains a few posts which I'm pretty sure don't exist. The URL ends with "p=xx" which means they were posted before I changed the postname format. These posts are not in my post list in wp dashboard. So how else can I delete them?
Maybe there are some article listing links. I don't use WordPress... but I use Joomla! and it can give out links that you don't know about. You should tell us what you have installed on your wordpress and click on the links to see what they show...
It's possible that your wordpress plugin uses separate table to store links. - try to uninstall it and install again - choose another plugin (thare are a great amount of them) If both cases do not work - it means you have garbage in DB, if you do not know how - ask any web developer to do it - it's just 5 mins of work.
Just create a new sitemap and upload that one. See if that solves this problem. Anyway regularly update your sitemap if you regularly update your content.