Joe,
1. Limit and ultimate load conditions normally need to be demonstrated by test unless the manufacturer can produce test data on sufficiently similar structural components. The catch here is in figuring out what is similar. As a very general rule of thumb, if two structures have the same or very similar materials, the same basic structural configuration, same type and magnitude of loading, same approximate size and has the same critical failure modes, then they are similar, otherwise they probably are not.
2. For ultimate load tests, the structure should contain damage at the critical locations that is the worst case of either 1) defects that would be acceptable per the applicable process specfication or 2) accidental damages (considering any potential growth) that will not be reliably detected by the aircraft structural inspection program. Generally fatigue testing for 2 "lifetimes" is used to demonstrate that these levels of damage do not grow in size (in composites, if the damages do grow then you will be stuck with a very nasty analysis, testing and inspection program).
3. Limit load tests for structure that must meet damage tolerance requirements should contain damage sizes and shapes that can be reasonable expected to occur but will not be immediately obvious to the pilot. Ofter these damages must be fatigue cycled for at least the loadings expected to occur for over two inspection intervals.
4. The only case that I have heard of where someone certified a composite structure for "safe life" (where damages grow under fatigue loading) is for some rotorblades. And I think that they used more of a damage tolerance approach (damage growth prediction linked to an inspection program; the safe-life approach is missing the inspection part). They had the potential for delaminations to occur and grow.
Two lifetimes (usually with a small load enhancement factor) is usually acceptable to the FAA to demonstrate "no-growth" of damages. If there is growth, then the number of cycles is going to have to be linked to the frequency and reliability of the planned inspection program, and will have to be negotiated with the FAA ACO.
You might look at AC29-2C, especially the Misc Guidance section 8 on Substantiation of Composite Rotorcraft Structure. I think that a major update and expansion of MG8 is coming out, but the current version is on the FAA web site.
You can also look at the paper on the 777 Empennage Certification Approach on my web site at:
Also there is a large chapter on Damage Resistance, Durability and Damage Tolerance in Mil-Hnbk-17, Volume 3, Rev F.
Hope this helps,
Steve