I've started one of these by trying to get the obvious pieces, like the BOs, then use the integrity checker to help me ferret out the rest. Is there a better way?
You're on the right track. I don't have a specific methodology, but the integrity checker is a life saver. I try to not let the integrity checker list get too big, but that's just my attempt to keep things relatively orderly.
Like you said you did, I'd focus first on the BOs and the relationships between BOs, then build from there.