My understanding is that this problem was alleviated with index-only scans in Postgres 9.2. Using these, each tuple no longer needs to be visited to check for visibility.
Index only scans work in some cases but not all. In order for an index only scan to be more efficient than a regular index scan, the visibility map needs to be up to date. This is a problem because (currently) the only thing that updates the visibility map is the vacuum and the autovacuum only runs after a large number of updates/deletes happen on a table. If your table is largely read/insert only, the only way to keep the visibility map up to date is to manually call VACUUM on your tables periodically which is a huge pain.