Have you seen any evidence that Google sometimes penalizes a page for too many internal links in comparison with external links? For example what if a page has 600 internal links and only 100 external links using Yahoo Site Explorer? I have this situation as I put some of my most important pages in the footer or sidebar of my content sites. Maybe it's just a side effect of having the same anchor text to the page so many times? But those pages don't seem to rank as well as I would think they would. I'm assuming this is a bit of a long shot but...
one thing you might want to be careful of is having to many links on one page. sometimes this may look like a link farm to the bots that crawl your pages.
Internal links have less weight then external links. Whilst good internal link structure is important, its no magic bullet on its own.
Possibly, but on the other hand, people do this with site maps, or lists of recent blog posts, etc. You probably just want to make sure that this isn't the case on *every* page. Also, if you're really concerned, you can decide on what pages are the most important in your site and SEO strategy, and no-follow all other internal links besides the links going to those pages.