I would just make it an opposed check... highest Int among the PCs +2 for every helper versus BBEG's Int (+2 for every helper, if any/possible; another +2 for successive similar checks).
I'm not concerned what the BBEG's skill check is. I'm concerned about what the DC is. Also you generally can't take 20 on a knowlege check you either know it or don't.
An Intelligence check isn't like a Knowledge check in that regard. You can take as many Int checks as you like to figure something out. It seems like in D&D its not about whether or not he will solve the puzzle, it is how long will it take him to do so (since divination magic exists). So, taking 20 becomes more of a hindrance depending on how long the DM rules it would take to make a check against the puzzle.
If you don't like Take 20, you can just make your roll + aid another attempts and the BBEG can make his roll + aid another attempts until he makes it, again, with time to take a check depending on the DM's ruling. Depending on the complexity of the puzzle, I would peg the time at between an hour and a day a roll. At a day a roll, a take 20 would take almost a month to complete!