I feel your pain. When I bought my '99 it only had a Valet key and trying to get a Master key made was a big pain. Toyota couldn't do it because the 4Runner was originally a Canadian model and they can't lookup info on cross border cars. The locksmith wanted $200 just to look at it and then probably another $100 to get the programming done, if they could actually do it.
I eventually found this Instructable:
https://www.instructables.com/id/DIY-Immobilizer-Hacking-for-Lost-Keys-or-Swapped-E/
Took the info off it and their reference documents and then build my own EEPROM programmer. Now, I have 2 Masters and 1 Valet.
So, here's my advise for you:
1) Are you sure you have a Master key and not the Valet key? A Master key will turn off the security light immediately after inserting the key. A Valet will hold a steady light for 1-3 seconds, then turn off. If you don't have a Master, then the programming instructions you outlined won't work.
Here are the programming instructions from RemotesRemotes.com. This is where I bought my key blanks from.
Tip: Try for 1 press-release per second. Steady and firm. Wait 1 second between steps, don't rush. It takes a long time for the keys to actually program. They say 60-80 seconds, but the first one of mine took almost 2 minutes. Just wait for the security light to stop blinking.
Note:
If I recall correctly, there was another instruction set somewhere that gave options for step 5. 1 press - Add Master Key, 2 press - Add Valet, 3 press - Remove All and add Master, 5 press - count keys stored. But, I can't find it now. (It could also be that my memory of this is from another system or car entirely!) This was for remote programming, my bad memory.
2) Regardless of Master or Valet, big box hardware stores (HomeDepot, Lowes, etc) can cut and program transponder keys. Check them out. You may have to buy one of their keys (I think around $40), but it will be an exact copy of your current working key.
3) "Virginize" the ECU EEPROM and start with newly programmed keys. You can go with the DIY route from the Instructable or software from
Immobilizer Cleaner Tool software [IMMOCLEN20] - $25.00 : OtherDeal.com, Automotive Electronics Car Computers ECU ECM Racing Chips Diagrams Service Software
Note: I can not and do not vouch for this software. I only know about it by following links from the various articles.