If you've lost all of your master keys, be ready for a tough, expensive battle. I just went through the process, and I wanted to document it for the library.
The valet key cannot be used to program new master keys, so having that won't help you (except that you can still drive your car).
A locksmith can probably cut new keys, and there's a hack you can do (
http://spyderchat.com/forums/showthread.php?44760-Lost-Keys-amp-Immobilizer-Fix) to reset the ECU and program new keys, but my locksmith wanted more than the dealership to do this and I didn't feel like buying all the electrical equipment (chip sockets/etc) to do it myself.
If you decide to go to the dealer you
must bring:
> Current registration (not expired!)
> The current, registered owner of the car (e.g. if it's in your dad's name, he must come with you)
> Your Photo IDs
If possible, you
should also bring:
> Printout of the programming procedure, TSB SS003-01:
http://www.mr2roc.org/misc/referencelibrary/toyotaservicebulletins/16specialservicetools/06.pdf
> The key code, which is stamped on a little metal plate that came with the car keys when new:
> Also, you may want to get all your junk out from the cubby behind the driver's seat.
-----------
In some Toyota models, the entire ECU/immobilizer has to be replaced if you lose the key. This is not an issue for us - our ECUs can be "re-seeded" (reset/reprogrammed) by the dealer. If you bring the TSB with you, it'll be easier to get a quote from the dealer. Otherwise, I've had a very hard time getting a straight answer on price.
Note: This seems to be a high-security ordeal. In CA, the dealer is required by law to file special paperwork to replace lost keys. They'll check your ID/registration, and it looks like even the tech's SSN is verified by Toyota when they request a new seed code.
-----------
Part 1: The physical key
First of all, you might want to go to the parts department so you can talk to them about prices. I saved $80 this way, as I'll explain later.
The master key is part # 89785-35020 "Transmitter, Transponder Key Master" - Get TWO. You want to keep a spare master key somewhere safe, that way you don't have to do the re-seed procedure if you lose a key again.
Be prepared for a surprised parts guy - all 3 dealers I went to said this was a really weird key, and only one dealer actually had it in stock. One dealer here wanted $50 each, but my parts guy says you should be able to get them for $26. Definitely ask your parts guy to match this.
Once you have the key blanks, the next step is to get them cut - this was $10 at one local dealer, free at another. However, if you don't have the key code (for the cutting machine), they might charge ANOTHER $10 to look it up by VIN number. The VIN lookup gives them the same code that is stamped on that metal plate. My dealer did both the cutting and code lookup for free (he did a VIN lookup to make sure the code on the plate was correct).
One dealer here wanted me to pay yet another $5 to cut a cheapo non-transponder key FIRST, just to make sure the cut was correct. The first dealer I went to did this for free. Good thing he did, because the key was hard to turn and got stuck when I tested it in the door! Turns out their cutting machine wasn't working right - a different dealer here cut keys with the same code and they worked perfectly.
Part 2: Programming the key
This is the hard part of the job, as you can see by the TSB I linked to. Because of the special procedure, I was quoted $390 by one dealer ($130/hr @ 3 hrs), $300 by another, then $200 by the last dealer. This is for labor ONLY, and is in addition to the price of the keys themselves. Supposedly some of the steps can take 10-20 minutes each - the write process is really slow and tends to fail a lot, forcing the tech to start over.
Bring all your keys with you - the new blanks, and your old valet key (assuming you still have it). They will have to re-program ALL keys into the ECU when they do the re-seed.
Get your stuff out from the cubby behind the driver's seat - The procedure says they need to jump a couple pins at the ECU. The guys at the service counter said it wasn't necessary, so I left all my crap (amp/subwoofer/misc cargo) blocking the way to the ECU. However, it looks like the mechanic did have to get to the ECU, because I noticed one of my amps was moved slightly and some wires were tucked away differently - I could tell he was very careful with my things back there, but it made the job that much harder for him.
Don't forget to ask for new dealership-quality key rings! Service dept should have them.
----------
Interestingly, I think my dealer may have reprogrammed my valet key like a master key. This means that even if I lose both master keys, the ECU will think that the valet key is a master key and let me use it to program more keys. The advantage to this is that I can create new master keys if I lose my two new ones. The downside is that if I give my car to a valet guy, he can program more keys too. I don't valet my car because I don't like people touching my car, so this is fine by me.
You can tell master/valet programming by looking at the immobilizer light (red LED near climate controls) when you insert the key.
No key: LED should be blinking (looks like a red blinking car alarm light)
Master key: LED stops blinking (stays turned off)
Valet key: LED lights up for a solid second or two, then turns off (no blinking)
Unprogrammed key: LED keeps blinking even though key is inserted. Car won't start.
----------
So, worst case, this would have cost me:
$50 key blank +
$50 key blank +
$10 VIN lookup +
$5 test key +
$10 key cut +
$10 key cut =
$135 subtotal, for parts +
$390 labor =
$525 for two keys
In my case, I only paid
$26 key blank +
$26 key blank +
$202 labor =
$254 total, and I got three keys (two master keys plus a free non-immobilizer key that I can still use if I accidentally lock my keys in the car or something).
----------
Aftermarket car alarms / remote start:
I have a DEI/Clifford/Viper remote start alarm (50.7x) with immobilizer bypass (PKALL). Because the immobilizer code changed in the ECU, I also had to update the PKALL. It's very easy - you basically unplug it, hold down the program button, then plug the connectors back in in the appropriate order (steps 2-6:
http://www.xpresskit.com/DocumentDownload.aspx?documentid=6403&productid=196&firmwareid=1636).
You should also do the "erase all remotes" procedure on your alarm and re-pair your remaining/replacement remotes, assuming one of your remotes was lost with the keys (see your remote manual for procedures - some remotes have different instructions).
-----------
As for factory keyless remotes, that's a whole separate ballgame. I didn't lose my factory remote, so I didn't have to worry about it.