Order-by and indexes

I need to get the latest entry of a large table matching a certain criteria.
This is my query:

SELECT * FROM "data" WHERE "data"."fk" = 238496 ORDER BY "data"."id" DESC
LIMIT 1

This query is quite slow. If I do a explain on it, it seems that it uses an
Index Scan Backward.

If I omit the order by on the query:

SELECT * FROM "data" WHERE "data"."fk" = 238496 LIMIT 1

It is very fast. And the explain says that it uses Index scan. This is also
very fast if there aren't any matches. But I've read that I'm not guaranteed
to get the correct match If I do not use a order by, postgres just returns
its fastest possible match. Is this right? But will not the fastest possible
match always be the first match in the index? Is there another way to make
the order by query go faster?

Thanks!

Odd-R.