This never happens to me. I'm using a CHMM installed theme. Are you guys using installed .cia ones?
You compile all the themes you want into a .cia file, including legit themes and custom themes and then install them all through a .cia installer. I then use the theme shuffler to utilize my current 10 favorite themes at that time, given that that fluctuates, my .cia file is about 70 themes or so right now, which makes for a .cia file that isn't huge, but still becomes something of a small inconvenience to have to reinstall if you ever enter and then leave the eshop. It's the only application that cause the themes to disappear in that way, so really not a big deal, ESPECIALLY if you never even have to enter the eshop again.