The list of programs for Open with… is maintained in the Launch Services database.
You can rebuild the database by the following command
he lsregister command, found at System/Library/Frameworks/CoreServices.framework/Frameworks/LaunchServices.framework/Support/lsregister, can tell the database to reset.
/System/Library/Frameworks/CoreServices.framework/Frameworks/LaunchServices.framework/Support/lsregister -kill -r -domain local -domain system -domain user
Note that utilities like Onyx or Cocktail can also reset this database for you.