Tempted by the belt sander, you seem to use that and the possibily-a-scroll-saw a fair amount. You need some affiliated links to your recommendations, a good enough for most people choice and maybe an upgrade choice too. Could even go for some Bit-tech branding on them.. Bit-tech mustache wax.. wait what was I talking about? Also on Dremels; when I were a lad in the late 90s it was the best tool I had for modding (plus a drill and 120mm hole saw) because I couldn't afford to have hundreds of tools. Later when I was at uni then for the first 5 years of my working life it was still great because the various flats didn't have room for much more. Now that I have a house with room for a lab and workshop with option on a shed it doesn't really get much action beyond sharpening things.
We've trained him well. He tagged the 'small ones' comment so we don't have to. I'm a little worried you've caught the Festool-itis, though. If you can't find the sandpaper you want: Hobby felt, glue, standard sandpaper paper sheet.
On the subject of sandpaper itself: buy the good stuff! 3M, Norton, Eagle, etc. Sure, you can get some el-cheapo paper from the local B&Q for 1/2 the price (or less), but not only will it clog up right quick fast in a hurry, when you grab a brush to clean it out and continue you'll find most of the grit brushes off too. And if you're very lucky, the grit printed on the back of the paper will actually match the grade stuck the the front! Oh, and one gotcha to be aware of: US grit ratings and EU grit ratings are not the same! If you had a nice stack of US rated 600-grip paper, then oh no! You just used the last sheet! But you have some P600 so you'll just finish off with that... whoops, now you have a bunch of new scratches!
I used a belt sander once, didn't set it down level and put a huge gouge in the material. I realise your taking about a bench top unit, but the first thing that come to my mind when I hear belt sander is the handheld unit. That's good to know
