I have been down this road, a few years ago.
To put it simply - the dealerships have no interest in you whatsoever - or your old vehicle.
Forget about them - they are not the answer for you.
As you found out - their first response is NO we cannot help you, then, if you don't just go away, and keep on badgering them, they may refer you to a secret, unnamed locksmith, only accessible through them - at an exorbitant price. They flatly denied the VIN key lookup thing, and - at the same time - claimed they were the ONLY possible source. They lied to me.
However - there was an answer to getting Lexus internal keyways keys made.
It took a determined search to find, but there was a local locksmith shop in my area (Mesa AZ) that had the blanks, and the special key cutting machine it takes to duplicate them.
Make a list of every single locksmith in town, start calling - if they say no - ask for a name that they know of who does it - keep at it.
Been a long time now - but $70 per key comes to mind - then.