I am always a little suspicious when frustrum culling becomes an abolsute necesity. Could your data be sorted pre-rendering in such a way as to avoid having to frustum cull so much data anyway?
For example BSP trees or portal rendering. If your data largly is static, BSPs allow rendering without depth-testing.
Perhaps you could use frustum culling but group your data in such a way so that large chunks of data can be culled by one test.
I guess my point is, if you are culling really small groups of objects, you may be wasting your time.