So I guess that your initial attempt is to iterate through all meshes in your scene, for each mesh, check all triangles if they intersect, right? The brute-force way.
I'm not sure if there's a lightweight library for you to solve your problem, but the problem is quite a large discussing area.
I would suggest using a bounding-volume structure, such as a KD-Tree used in 3 dimensions. Christer Ericsson suggests an implementation in his book "Realtime Collision Detection" which is cache-friendly and memory efficient. I've implemented his suggestion in a project and indeed it did turn out very well. The task of creating a KD-tree together with splitting your meshes into well-balanced tree's is covered in depth by Ingo Wald (http://www.sci.utah.edu/~wald/Publications/index.html). I suggest you read up on there. The Surface Area Heurestic (SAH) is considered (one of?) the best algorithms for KD-splitting, Ingo Wald covers it in one of his publications (http://www.sci.utah.edu/~wald/PhD/index.html).
There are a variety of freeware KD-tree's out there, I haven't really looked into kdtree at google-code (http://code.google.com/p/kdtree/) but it looks pretty decent. There's some interesting tutorials (http://www.autonlab.org/autonweb/14665/version/2/part/5/data/moore-tutorial.pdf?branch=main&language=en) that you can read.