bpy.data.meshes.new gets slower and slower
Not a real answer, but more of a workaround : I manually merged the meshes by fiddling with the vertices arrays. So instead of creating 3000 meshes, I create only 1. Works in my use-case.

If it can help someone else, it looks like this:

lAllVertices = []
lAllTriangles = []

for fileToParse in allFilesToParse:
    lVertices, lTriangles = ParsePolygonalRep(fileToParse)

    # Before extending lAllTriangles, fiddle with the indices
    lCurrentIndexCount = len(lAllVertices)
    lTriangles = [(x+lCurrentIndexCount,y+lCurrentIndexCount,z+lCurrentIndexCount) for x,y,z in lTriangles]

    lAllVertices.extend(lVertices)
    lAllTriangles.extend(lTriangles)


lMesh = bpy.data.meshes.new(lMeshName)
lMesh.from_pydata(lAllVertices,[],lAllTriangles)
ob = bpy.data.objects.new("tmp", lMesh)
bpy.context.scene.objects.link(ob)