The exact limit is really hard to determine ahead of time.
One thing most people underestimate is the high requirements that an index must fulfill, before it becomes a candidate to be used in a query.
An efficient (nonclustered) index
offers great selectivity, e.g. returns only a very small percentage (< 1%, < 2%) of the total rows. If the selectivity is not a given - SQL Server's query optimizer will most likely ignore this index
should ideally cover the query, i.e. return all teh columns required by the query. If you can create an index that has 1 or 2 index columns, and includes another handful (2-4) columns as included columns and thus you can cover a query - then chances are the query optimizer will use this index. Which also means: if your code is always using
SELECT * ..... to fetch all columns, the likelihood of indices being used goes down - quite dramatically, actually
I'm sure there are a ton of other criteria as well - but I would believe these two are the most critical ones. Of course, you should always keep your indices properly maintained (reorganize, rebuild) and make sure the statistics associated with your indices are up to date.
PS: nonclustered indices on foreign key columns are a special case; by default, I would always recommend adding those, since they help speed up both referential integrity checks, as well as
JOIN's on those FK constraints. But even here, it's absolutely valid to "extend" those FK column indices by adding some additional "include" columns to make them even more useful.