I'm unclear about if Sitemaps and SEO and WPMU Dev SEO are supposed to compliment each other or if one is preferred over the other in some situations.

Near as I can tell, DEV SEO is more comprehensive, but Sitemaps and SEO submits to search engines and Dev SEO does not(?).