I think I have seen many different posts on this already. People keeps reminding others about putting a Privacy Policy page if you app happens to connect to the Internet.
I already have a published app on the Store, and this time is my second one. I always remember about the requirements so I put a setting for Privacy Policy right from the beginning and linked it to a page on the app website. The problem was I had not implemented the webpage at all. The situation at that time forced me to publish the app rather early, so I decided to put the website later, after I had submitted the app, when the certification was going on.
Pushing the website back was a good idea and it helped me to finish the app on time, but it turned out to be not a totally good. One may suggest that I should have put a basic page for the Privacy Policy and delayed the rest, but the problem was more complex than that. There were actually 3 pages that need to be implemented for the certification: the Privacy Policy of course, the How To page (I included this setting as well, thinking that this could help me to put work later, even after the app is published on the Store), and surprisingly the home page as well (I put a link to the home page inside the About settings). The home page surprised me because I thought I already have it there, but then I realize the testers also rejected the current blank home page (with a default Index header on top); this was regards as incomplete functionality of the app.
So next time I will have to note down every link I have inside the app, making sure that I do not forget any of them before a Microsoft tester starts to fail the app!
And I would say, this is painful.