I've been using Instapaper (mostly on programming related blog posts [standard WP/Blogger templates] and major magazine articles [Vanity Fair, Economist, etc]) for a while and rarely found this to be the case. It has almost always stripped unneeded markup well, often providing a superior reading experience on the iPhone than iOS Safari's rendering of the original content.
Are there any specific sites/types of pages you've had trouble with?
My only real complaint about Instapaper is that it often seems to strip out the byline, and sometimes even the name of the publication, leaving me without some of the context I like to have when reading an article. (Here's an example of missing byline: http://www.instapaper.com/text?u=http%3A%2F%2Fwww.bookrags.c... (the article is written by Zadie Smith, which I find to be very important information.))
Are there any specific sites/types of pages you've had trouble with?