Should foreign keys always be indexed?

In my opinion, mostly yes. The query optimizer will make a decision on whether it will be faster to use it or not. Indexes may not be of much use for low cardinality reference columns and will not be used by the optimiser.

On a Star Schema there may be some benefit from indexing low cardinality columns. This will give the query optimiser the option of using index intersection.

Foreign key indexing may not be desirable for purely data warehousing tables that are frequently batch loaded. The index write traffic will be large if there are many indexed columns and it may be necessary to disable foreign keys and indexes for these kinds of operations.

A more obscure reason for ensuring foreign keys are always indexed is the following - A delete from the parent table may lock the child table, which may result in a deadlock.