Thanks for your responses, they were quite helpful.

I got back to the problem and as suggested I recomputed the statistics
for the two tables. Once I have done that the optimizer stopped using
natural and started using the proper index, even with the original
query (after recomputing the statistics the original query became as
fast as the left join!). The original query switched to using
PLAN SORT (JOIN (PVL INDEX (RDB$FOREIGN72, RDB$FOREIGN73), PV INDEX
(RDB$PRIMARY39)))

Now, I will rewrite the query to use left join in case this happens
again. However, it seems that this problem might affect other queries
as well.
The easy fix would be to force regular statistics updates on all
tables or maybe even do a backup-restore more often. This specific
database was up for a week, and in the worst case we do a monthly
backup-restore. Currently we don't recompute statistics as we expect
the backup-restore to take care of that. Running a nightly maintenance
script (at least recomputing statistics) will the probably fix all that.