As the queries are kinda complex would it be an acceptable attempt to limit the maximum depth of user creation? If we limit the depth it would be simple to do a 'created_by=user' OR 'created_by__created_by=user' ... OR ...'created_by__created_by__...__created_by=user' query. I would then add a 'depth' property to the CreatedBy models which can be used to make sure that the maximum depth is never exceeded. That CMS_MAX_USER_DEPTH could even be configured via the settings so arbitary complex user hierarchies are still be possible.
Another point is regarding the deletion of users. What should happen if a user is deleted that created other users? Should it also delete the users that are now left over without a creator?