I finally managed to reach the bottom of the Lake Cave. The key is to start early, have a reasonable amount of food with you, and hope you are lucky. You have until 5AM, when you will be sent home automatically to start a new day.
It turns out you can use the hoe to scrape the floor looking for an entrance to the next level. This is an excellent plan, as the holes become more and more likely to kick you back up to an earlier floor, the deeper you go. The downside is time - digging with the hoe is a slow business, so it's best to get as far as possible through random falling through holes before traversing the last few levels manually. On this outing I managed to get to level 93 through random falls before beginning to dig. I would recommend trying to reach at least level 90 before starting with the hoe.
The strategy I employed was to dig for holes in a radial pattern moving from the stairs outwards. Or, if you walk around slowly, you should be able to see 2 black lines (glitch) around the square that holds the stairs. The hole to the next level tended to be fairly close to the stairs, in the 3x3 area around it. I've found that if you are one level above the "special" levels (15,20,25,30,35,40,45, and 50) or in the 90's, the hole was not so close to the stairs. The hole was never hidden under a rock.
One final tip - if you are trying to get to the bottom of the Lake Cave, bring a fishing rod. I didn't and was annoyed. Deeply annoyed...