As far as I'm aware, you basically need to write a test method that generates all of the combinations (or calls the factory and iterates through the items) that calls your original test (now no longer a test method) a bunch of times.
Unfortunately, these do not show up as individual tests in results - they show up as just one test- so you have to pretty explicit in your error output. This means that as with this approach, as soon as one fails it stops the rest (you can get around this by keeping a big list of results, but that's yet more overhead)
I'd think twice before going to mstest right now unless you have to - the lack of a test runner on a clean machine is killer, and it's neither extensible nor frequently updated.