Okay, I finally got one to be solved! I still suspect the shuffling process can produce inversions that can't be resolves via sliding operations.
No, the board is randomized by swapping random tiles. I'm pretty sure now that all puzzles are solvable, though mid-board spaces do add a little extra mental barrier. I've run into 2x2 grids that I can't get but then a friend solved them very quickly, so I think there are just little niches our brains end up in that we can't shake out of. I might be wrong though!