Inclusion of ORDER BY on query that returns no rows drastically affects performance
I agree with Martin Smith's answer, but the problem is not simply one of statistics, exactly.  The statistics for the foreignId column (assuming automatic statistics are enabled) accurately show that no rows exist for a value of 3 (there's just one, with a value of 7):

DBCC SHOW_STATISTICS (tinytable, foreignId) WITH HISTOGRAM




SQL Server knows that things might have changed since the statistics were captured, so there might be a row for value 3 when the plan is executed.  In addition, any amount of time might elapse between plan compilation and execution (plans are cached for reuse, after all).  As Martin says, SQL Server contains logic to detect when sufficient modifications have been made to justify recompiling any cached plan for optimality reasons.

None of this ultimately matters, however.  With one edge-case exception, the optimizer will never estimate the number of rows produced by a table operation to be zero.  If it can statically determine that the output must always be zero rows, the operation is redundant and will be removed completely.

The optimizer's model instead estimates a minimum of one row.  Employing this heuristic tends to produce better plans on average than would be the case if a lower estimate was possible.  A plan that produces a zero-row estimate at some stage would be useless from that point on in the processing stream, since there would be no basis to make cost-based decisions (zero rows is zero rows no matter what).  If the estimate turns out to be wrong, the plan shape above the zero row estimate stands almost no chance of being reasonable.

The second factor is another modelling assumption called the Containment Assumption.  This essentially says that if a query joins a range of values with another range of values, it is because the ranges overlap.  Another way to put this is to say that the join is being specified because rows are expected to be returned.  Without this reasoning, costs would be generally underestimated, resulting in poor plans for a broad range of common queries.

Essentially, what you have here is a query that doesn't fit the optimizer's model.  There's nothing we can do to 'improve' estimates with multi-column or filtered indexes; there's no way to get an estimate lower than 1 row here.  A real database might have foreign keys to ensure that this situation could not arise, but assuming that is not applicable here, we are left with using hints to correct the out-of-model condition.  Any number of different hint approaches will work with this query.  OPTION (FORCE ORDER) is one that happens to work well with the query as written.