I stand corrected, you need 2 previously programed keys and then you can follow the instructons in your owners manual for programing extra keys. At least my 2000 f150 manual has this info. It also has the info for programing a new remote when you have lost one. I would be more than happy to relay the info. for remotes if you like but it sounds like the dealer is going to have to help anyway.
I would purchase another key and have three on hand so If one is lost you still have two to program with. By the way you can only add extra keys 8 times. After that it won't accept any further attempts.

2000 XLT Flare Supercab Sport 5.4-Auto-355LS-Tow pkg-Bedrug-Xtang Tonneau