There are a ton of options. This is a situation where I doubt you will avoid a good bit of hand cleanup. No matter what method you select, for this type of job, I'd do all of the cuts a couple thousandths short, then a final pass to free the parts, so the cutting forces are low when the parts free.
Some that I have used in similar circumstances are (starting with the ones you reject):
Two sided tape. Run the tool path very slightly shallow to keep the parts from floating and separate after machining. A little clean up is generally needed, and with adhesive, a fair bit will be to remove it anyway. A thin edge on MDF will usually break off cleanly with no tools needed.
Tabs to keep the parts together. This is a common strategy, and many CAM toolpath generation tools provide this as a standard option. Again, this requires post-machining cleanup
Vacuum table. This is about as good an option as you get. This would usually be made for the job (or job class) at hand. For many things, a shopvac provides sufficient, if loud, vacuum (about 1/3 to 1/2 atmosphere). The prework for this is more than most people would want to deal with for a one-off job.
Solvent-cutable adhesive. I have used cyano-acrylates for this. After machining, acetone to remove.
Use top-side hold downs. Do most of the cut, pause to install a hold down for the soon to be free parts, then finish. This is a pretty standard technique. If I were doing a flat (jig-saw style) puzzle with pieces in the 25mm range, I'd use 12.5X25mm section aluminum bar for the hold down, tie it at both ends, and tie it about every other part along the length.