I doubt that the paper used for egg cartons has been recycled many times - where would you source such a thing as over-recycled paper in large quantity? Yet, it does not seem to be of high quality. In Berkeley, we recycle egg cartons with #3 Super Mix or #6 News. They are a very small percentage of the total paper we receive and so do not present any problems.
I know the farmers' market folks sometimes have trouble from the health department for reusing egg cartons although it is still generally done. I pull cartons from the paper pile to use for my chicken eggs with no complaints from customers.