The best methods we have (afaik) basically randomly position the object and then nudge it until it gives up after doing lots of tries

I'm skeptical. I can think of some problems that do work like that, like graphviz's node-cluster-and-fit-to-a-plane layout stuff. But here, you should just need to be working with the convex hull. It should be possible to eliminate a lot of classes of potential solutions by reducing it to looking at edge cases, like some face of the convex hull is in-plane with the bounding box or something.

kagis

Yeah.

https://en.wikipedia.org/wiki/Minimum_bounding_box_algorithms

In computational geometry, the smallest enclosing box problem is that of finding the oriented minimum bounding box enclosing a set of points. It is a type of bounding volume. "Smallest" may refer to volume, area, perimeter, etc. of the box.

It is sufficient to find the smallest enclosing box for the convex hull of the objects in question.

In 1985, Joseph O'Rourke published a cubic-time algorithm to find the minimum-volume enclosing box of a 3-dimensional point set.

It is also possible to approximate the minimum bounding box volume, to within any constant factor greater than one, in linear time.

EDIT: Though if OP is rotating along anything other than just the up-and-down axis (is that, by convention, Z for 3D printing? Been a while since I've printed anything), it's more complicated than just determining whether a rotated object will fit in the bounding box, because 3D printers have their own constraints in things like the overhang that they can do.