You don't even have to test all 8 verts, you only need to test two opposing verts (the ones that extent farthest in the direction of the plane's normal). If you store the box using a center vector and an extents vector, just take the component absolute of the normal of the plane and dot that with the extents, call this x. Furthermore dot the (non-absolute) normal with the centre of the box, call this c. The box projected on the plane's axis is from c-x to c+x. But for a frustum test you're only interested in the smallest value (c-x), which you have to compare to the plane's distace to the origin (usually -d).
A further optimization can be made by the fact that lots of boxes have the same 'x' value as their size is the same, so you're left with a single dotproduct per box.
Even then, many of those cases can be dispatched by doing a sphere test first.
Actually, for octree usecases, most false positives come from boxes lying near a frustum's edge. Casting a sphere around the box doesn't help in this case. If you are GPU limited and can spare some CPU cycles, it might be feasible to do a full SAT test by precalculating some support planes using the frustum's edges and the unit axes (as all boxes in the octree are axis aligned)