Yeah, that stinks. There was a pre-built mine outside of my base that I claimed just to keep from having a neighbor and the cave-down happened on the third tile I mined.
This is level one of the mine that was in my base, and I had lousy luck finding the first cave-down:
http://i.imgur.com/2iQHGVd.jpgI pretty much did what you did at first, then I said screw it and I went and line-mined far away from the entrance and found the cave-down pretty quickly:
http://i.imgur.com/6HWj3wp.jpgJust hang in there. The first cave-down is usually easy to find, but not always. When I hit the 2nd level I immediately found silver ore and dark tile that led to the cave-down in the same day:
http://i.imgur.com/OBixbUM.jpgBut yeah. Now I just line-mine in the four cardinal directions when I hit a new level. Another good thing about that is you can click the ladder and then switch to a browser tab or something and then come back and you're on the previous level again, and can drop the boulder in the huge empty space created by the cave-down.
Edit: Also, when you line-mine, and you place a support when you hit a dark tile patch, and then you start mining it out beyond the radius of the mine support, you can then go farther back in the long line you mined and make an L-shaped tunnel around to the back of where the dark tile you are mining is. Then, you can see if the dark tile extends far enough to warrant using another mine support. Alternatively, you can just spam mine supports.