Hi Luke
To include the suggestion on searchenginewatch.com in this conversation, it said:
Submit an updated sitemap to Google Webmaster tools and use the change of address function if moving to a new domain. Remember to initially keep the old URLs in your XML sitemap to facilitate Google crawling those links and processing the changes in their index.
Well it would be interesting to hear others feedback on that. Personally, I think having old URLs in a sitemap (that without a redirect would result in a page not found 404 error) doesn't seem correct to me.
Presumably, you have had the URL in the sitemap previously when the page at the URL was active. But then, by setting up a 301 redirect, you are telling Google that the page at the URL that Google has in its index has now permanently moved to a new URL.
When you submit a sitemap to Google then you are submitting a list of all the URLs on your site that you are asking Google to crawl. But to include the old URL in your sitemap along with the new URL is essentially asking Google to crawl two URLs pointing to the same page.
I'm not sure Google would necessarily consider that to be a canonical issue (because the old URL is now not current) but for me it's a misuse of the sitemap.
But as I say, it would be interesting to hear others feedback on this.
Peter