How much enlargement is too much enlargement is just a very difficult question to answer. I can give some observations from a "fine art perspective" that might be somewhat illuminating. Or not. IDK.
A few years ago I helped hang an exhibition of prints from George Eastman House. The exhibit was of old Vietnam war photographs. Just about all of the B&W was 35mm Tri-X, most of it developed in the field under very primitive conditions. Needless to say it was all hand held -- no tripods, no mirror lockup, etc. The photographers had more important things to do than optimize for sharpness -- like trying to stay alive in a fire fight. Literally.
There were several prints in the group that GEH had printed 40 x 50 inches. They were soft, grainy, and very sadly beautiful. One image in particular continues to haunt me, so I'd have to say it was quite effective at that size. People at the exhibit would look at it from across the room, from the "proper viewing distance" and they'd walk right up to it. And come back to it over and over. It seemed to work for a lot of people, not just me.
So under some conditions, some images can easily handle 35x enlargement.
That said, very very few images can do that. Very few.
On the other end of the spectrum I've got a few 4x5 negatives, Tri-X, that I pushed a couple of stops. After about 4x they flat out start coming apart. Nice images, but I can't really print them above 16 x 20 inches because the graininess doesn't serve the image well at all.
I've also got a nice image on 4x5 400PortraNC. The lab did a fine job on film processing, and I did a reasonably good job of capture in a strong wind (snow storm). It's nicely detailed, but I can't take it much above 8x because again, the graininess becomes intrusive and draws the viewers' attention away from the image and the detail in the image. It's just the way this particular image works.
So... how much enlargement seems to be one of those things best done on a case-by-case basis. It's just a huge multi-variable equation involving everything from image capture on down the processing line to final print. I wish there were simple rules of thumb that really worked. But if there are I have yet to find them.
Someone on here quoted really good 7x-8x enlargements from scanning on the Coolscans. I have pushed a little bit beyond that comfortably - about 10x (so 10x15 inches from 35mm, and 20 inches from the 6cm dimension on 120 - 16x20 from 645, 20x20 from 6x6, as much as 20x30 from 6x9). How much beyond that (for a really good print of a high detail subject) will an Imacon go? A drum scanner? I can't imagine getting 20x, because that was widely considered impossible in the chemical darkroom (that would be a 20x30 from 35mm, and any print that size from 35mm I've ever seen was a grainy mess, no matter how it was produced). Is 15x realistic? A good darkroom worker could ALMOST do that, IF they started with a really good negative or chrome - that's where the special developers like Acufine and Microdol came in - people trying to make detailed 16x24 prints from 35mm. Of course there are low-detail subjects (or places where grain is acceptable) that print significantly larger, but that's true of digital as well.
The best digital sensors today will go something like 25x on the physical size of the sensor (I use the D3x as an example, because it's what I use, but I'm sure that there are other sensors that are in the same range). That gives us 24x36 from full-frame 35 (I do that all the time, and it looks great), 33x44 inches from the smaller medium-format systems and 36x48 from the P45+ size sensor. A P65+ with its oversize sensor SHOULD print right around 40x50, which is, coincidentally, also a 10x enlargement from 4x5.
There are a couple of problems with this... First is depth of field - I find myself REALLY thinking hard about DOF on big prints (using a bigger camera, one often has tilt to help deal with that - of course this is a problem with non-tilting medium format as well). My next lens purchase will certainly be a PC-E Nikkor (I'm trying to decide on focal length now). The second issue is when do you not actually need any more resolution for a bigger print, because of viewing distance? Ansel Adams raised this question in The Print in his chapter on very large prints. My 24x36's look good from a foot away - could I make a 40x60 that held up at 3 or 4 feet? If so, who'd ever look at a print that size from any closer than that? Prints that big are often displayed in ways where you can't GET closer than that...