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.