The product URL Key is stored in catalog_product_entity_varchar and the attribute ID for it can be found in eav_attribute.
Nope, the URL Rewrite is stored in that table and the parts of its stored paths in system rewrites are made up from the product key stored in the aforementioned table and the category URL key in another table. If you make changes to it, they will be overwritten during a Catalog URL Rewrites reindex operation. Kind of like how inserting stuff into the flat products table gets overwritten when that table gets reindexed.
However, this may be the solution. If your URL Keys are correct when you go into product maintenance and displaying wrong when you go to the actual web page, then you may need to go do a reindex on the Catalog URL Rewrites index so it will recreate the entries from the URL keys in the product and category entries.
I know this from having had to get overly familiar with it during importing a couple thousand custom 301 redirects.
Why two tables? It’s actually three. The URL key is an attribute of a product. In order to store this item in the EAV system, the product itself will be assigned a productID in the category_product_entity table. The attributeID is defined in the eav_attribute table. The actual VARCHAR data is stored as values in yet another table named catalog_product_entity_varchar. You reach the value by searching for the row keyed by attributeID and productID.
You’re not dealing with a relational database system here, so you can toss out everything you know about how other shopping cart systems work.
Magento expects each product URL key to be unique, just like each SKU id needs to be unique. The only reason it should not let you change it is if it already exists for another product. Then Magento usually pastes a -1 (increments for each duplicate) to it.