This is such an obvious problem that I expected to find an answer using Google straight away. Maybe my search skills failed me but it took me a good while to find the right answer for Leopard, which is why I want to share it here.
There is this article on Lifehacker. However, the article itself has it wrong; the real solution is in a response by "mtts" halfway down the page, and even then the command doesn't work as described on Leopard. What did the trick for me, on Leopard, was the following command:
/System/Library/Frameworks/CoreServices.framework/Versions/A/Frameworks/LaunchServices.framework/Versions/A/Support/lsregister -kill -r -domain local -domain system -domain user
There is no manpage for lsregister but invoking it without any arguments will display some help.