That could be an option, but then it would be better to also add the inserts in the base plate so you can use those to clamp your workpiece.
As I want the base-plate to be my flat reference. and just want to mount it once and never touch it again, my intention was to put a wasteboard above for which it isn’t a problem that it gets damaged. And potentially in a slightly softer version of MDF.
That’s why I wanted to create a topic to collect different ideas before spending hours making stuff and see someone else come up with a much more elegant solution 
I do like the idea of the slots and actually it was on my mind too. Not in the tilted way you described (which is quite fool-proof) but with tradtional t-slots. And then a lever on the side to lock it. 2 slots front to back and 2 levers on the front and on the back would be enough I think.
Or a catching latch (not sure about the terminology here
). Basically like a dowel pin sticking out of the base, from the side a “hook” type latch that catches it and as you close it also tightens it.
Something along the lines of this (but also pulling it closed, not just latching):

Another variant is like a “chest-lock” or the type of spring locks you have on a spring-form used for backing. like this:
But with both of those options I was struggling as where to attach those. For the box lock I was thinking underneath the base plate and have them pull down on the front and back, but you don’t have that much space at the bottom to put these.
Yes! That’s where the inspiration for the cross-shaped cut-outs came from!
Why not just use round dowels? The projects I’ve done with two sided milling have learned me that if you just put them in wood, the holes will start to show some wear and they will get loose, so i wanted to use the cross shaped section to make it less susceptible to this. (because there is friction in all directions. Another solution would be to make the holes a bit bigger and insert a piece of tube to avoid that wear.
Your idea is also along the lines of what @brent113 mentioned in this post: New quick toolhead change print - #15 by brent113
That was my first idea in combination with the box-locks, but I failed at finding a good place to attach those.
So should I consider this to be like a sort of velcro on steroids? Or does it also help to align the two connecting pieces?
Finally some updates from my side:
I have been tweaking the model a bit more and cleaning up the openscad code a bit. I intend to have it online on github soon. Mostly to make sure I do proper version tracking for myself as well 
It came out pretty well (on the right hand side you can see that the toolhead doesn’t reach far enough to make the cutout of the handle. Left and back work out just fine. The front just falls short but you can easily break out the remaining piece.
The good news is that all holes align up perfectly (yay!). I did do a quick test by running a calibration with the 3d print heat and just the sheet on top of the wood and it looks pretty good. There is still a deviationm but the surface is flat, just tilted. (hence the idea of machining it flat. Or this board could just be shimmed.
I modified the through holes for the carriage bolt so I can fix those to the build plates with a washer and nut from the bottom as well. (in stead of just having the hole there. Should make installing easier.
And as they say: measure once, cut twice (or how exactly did that go?
)
The location of those through holes is actually ok. It’s about 7mm away from the carriage. Which is ok for a normal bolt, ok for the type of clamps I first intended to use there but not for the wing nut I wanted to use for initial testing.
Nevertheless, good enough for a first iteration and doing some more testing with it.
But because magnets are fun, and it would cooler if I didn’t need screws/clamps at all, I finally did order these (pot magnets):

25mm diameter and supposedly 18kg of pulling force.
I chose those with the threaded barrel so they can easily be adjusted in height if needed. (and to prevent having them glued in place and just ripping them out every time because the magnet is stronger than the glue.
combined with these:
because they have a small border, that will prevent them from sliding away.
I figure that 3 or 4 of those magnets in the base plate should be enough to keep it in place.
Or maybe even already impossible to remove without a crowbar 
I’ll be trying out some more stuff later this week, so if you think I should try something else as well, do let me know!