I recently did some work on a site that was having trouble getting indexed. The site is a technical magazine for a specialist audience, with new material published monthly and much of the content only available to subscribers.
(The structure and design were not something I touched. Navigation was disrupted by some alterations to directory structure and navigation was written browser side by script, which, I think, the search engines don't detect.)
The attempted solution was to create a sitemap and let the search engines know about it.
Tool used was the Google sitemap generator (Python program) fired by a batch file, so it is a one-click process that probably takes less than a second.
Search engines were informed by submission of the sitemap and listing the sitemap in robots.txt. The submission process worked with Google, the others I'm not sure.
I only followed progress for a few days. The results, as I recall them were:
1) Live and Yahoo picked up the sitemap within 24 hours.
2) Google was reading it within 3 days.
3) Soon after reading the sitemap, the listed pages were spidered.
4) Appearance in search results not checked yet. (I may check it later when I've settled into my new country.)
1. Sitemaps really do work.
2. The results are quick, a few days.
3. The path to getting into results will take a little longer, the sequence is a) read sitemap, b) spider listed pages, c) add to index (I have not investigated what determines the timings).
4. List in the robots.txt.
I've also written a custom sitemap generator (using Powershell). This was needed to implement some requirements that the standard generators don't implement (as far as I know). One of those requirements is honouring a robots noindex instruction on individual pages. This takes more effort and skill than just latching onto an existing program.
In a world where the engines no longer index everything they find, I suspect, that site owners, who help the engines, get some sort of edge. (If anyone has some thorough research on that I'd love to see a link!!)