Barring the possibility of Apple ever laying down clear, comprehensive, stable and reliable guidelines for avoiding rejection (with many real, anonymized examples), it sounds like the MVP approach is the best way to go.
Rob's case is special, though, because his app was never actually rejected. I suppose if he'd been willing to submit a MVP and wait the same amount of time in limbo before putting any more effort into it, he could have saved himself all that hard work. But the aggravation of not getting an answer would have still sucked.
The quiet issue that most people don't hear about are not initial submissions, but updates that get stuck in the same review limbo for months and months. My app has been on the store for nearly two years, had many incremental updates, and my iPad compatibility update (not even a new app) has now been in review for 3 months. It's really hard to explain to your existing userbase why you cannot get an update released. Many of them aren't even aware that Apple can be the bottleneck for such a long time.
That's true. There really isn't a good way to communicate with your userbase. You're basically limited to updating the app description and hoping your existing users bother to click the "More" link to read it (assuming you didn't put the update at the top, because that's prime real estate for attracting new customers).
It really astounds me hearing about how long new apps and updates can get stuck in limbo, with no feedback from Apple or path to action. So far I've managed to avoid any nightmare scenarios, but every new anecdote I read makes me increasingly anxious that one day, that time will come.