You can totally compress marshmallows*, and you're very close to the right idea with the vacuum bag.
A couple months ago, I bought a vacuum pump and bell to degas liquid silicone (to prototype the custom stopper for my Backcountry Boiler :) ). Remembering middle school science class, I tested the vacuum I was drawing by putting marshmallows in the bell. At first (as James points out), they get huge as the air bubbles expand. But then the air bubbles burst, and when you remove the vacuum, they're about half their usual size and really dense. As Sarah points out, they'll never be the same, but it's a lot of fun!
*I'm quite sure this is not helpful at all, but I wanted to share. :)