Those can most certainly be rekeyed. The top plates are staked in, but they can be removed and restaked. Any REAL locksmith can perform this operation. You've been talking to key monkeys...

I'm not a real locksmith, but I could figure it out and probably get a key cut. I can tell how the good locksmiths do this without taking a lock apart, but you need a fresh uncut key. There are marks inside the lock that can be transferred to the new key by inserting and pressing the key against the sides both ways, sometimes...