Solution: If the Devices block Teleportation-type effects,
Stop right there. I never said they block teleports- I said they block FTL. There's a very big difference. Teleportation is instantaneous; it's a change in spatial location without any move in time along with it. faster-than-light travel is standard movement that happens to be what it says on the tin- faster than light speed.
Further, how can the PCs teleport black holes?
A black hole- meaning, the event horizon that forms around the singularity- is as easy to transport as the singularity itself. It travels with the singularity, and so if you can influence the motion of the singularity, you move the whole black hole. Teleporting a black hole is therefore easy, if you have a means of getting the singularity in the effect; and since the PCs were using a teleport effect that hits entire volumes at once rather than specific objects, it was fairly easy for them to catch the entire event horizon of the black hole they chose within said volume.
(Speaking scientifically here) Shouldn't that require limitless amounts of energy?
Speaking scientifically, no more energy than moving it at all would.

Or more precisely, no more energy than would be required to move any other object given the parameters of the effect being used- which in this case, as I said above, moves an entire volume of spacetime without regard to what happens to be inside it.
Or are they doing it via magic, and the spell only cares about volume?
My games combine science and magic, actually. I've never gone for the notion that the two are somehow opposed; that always struck me as silly- and often a lazy throwaway dismissal of any attempt to make something that uses both. I'm certainly aware that some people just plain don't like to mix them; I don't happen to be one of them.
I don't know much about your setting, but I know I would not let the party be teleporting BLACK HOLES around willy-nilly... Who knows what extra-dimensional entities might take notice of that kind of thing?
Believe me; that's the least of what they've done- but I also have awake Sidereals in the setting within which they did this stunt. The Sidereal of their universe had explicitly told them that she'd be MOST upset if they did something that disrupted the large-scale gravity map of the universe. That was why they were careful to pick a mere stellar black hole, which doesn't really affect anything beyond a light-year or two. So yes, they have been drawing attention- but they've also spent a lot of time recently going around getting allies among the awake Sidereals for the eventual battle against the Demiurge when it wakes up. The Sidereal of their universe was actually one of their first such allies; they gave her critical information which let her find a way to create a portal to the Eternal Realm and thus have an escape route ready if the Demiurge does win. So she's inclined to be indulgent with them. Really, it would have been unreasonable in the extreme for her to do anything after the black-hole-kill but clap appreciatively from a long distance.
But, thanks for trying anyway.
