Incorrect statistics are used on index seek
The estimate for the inner (lower) input to a nested loops join is per iteration in SSMS. The 'actual' number of rows shown in SSMS is a total over all iterations. This often causes confusion, and is the result of a questionable design decision.

The one row estimate therefore needs to be multiplied by the estimated number of executions. Many people prefer to view plans in SQL Sentry Plan Explorer, which does this for you, so the numbers are directly comparable (both estimate and actual are shown over all iterations).

Using a temporary table to materialize a relatively small result to improve cardinality estimation is a very valid tuning technique. If the code executes as part of a function or stored procedure, you may need to manually update statistics on the temporary table and request a recompile to get the best plan in some circumstances, see my article Temporary tables in Stored Procedures for details.

There are still times when the optimizer will choose the 'wrong' join type even with good cardinality and distribution information, but these are relatively rare. You certainly maximize your chances of getting a good plan by ensuring the optimizer has accurate information to base its decisions on.

I realize this answer is a bit generic, but there's only so much to be said on the basis of a couple of partial execution plan images. If you add showplan XML for both queries to the question (link to an off-site host e.g. gist), I might may be able say more.