I know this answer comes a little late, but I've just picked up on MvcSitemap myself in the last week and am using it as per the OP's question in my own project.
It's certainly achievable. You can define sitemap nodes by creating a custom node provider, within which you pass in the route values for each node, based on the custom route you mentioned. Even version 1 of MvcSiteMap allowed for dynamic nodes, but v2.0 seems a lot more flexible - and it supports MVC2 Areas.
Have a look here for more details. The sample project is pretty good too. If you only have SQL Express installed, you may need to grab the DB files from the original MVCMusicStore project as the DB files included with the MvcSiteMap sample will only work on paid versions of SQL server.