Say i have a one-to-many lookup relationship between 'Parts' and 'PartsCategory' objects. Something like say the following example records:

Part, Price, Brand, Model, CategoryCode:
Front fender, $40.40, Mercedes, A-class, 10.23.4
Rim, $80.00, Chrysler, Voyager, 23.10.4

Category, Location, Manager, Code:
Plastics/Protection, Warehouse C, John Doe, 10.23.4
Wheels, Warehouse F, Jane Doe, 23.10.4

If i create a lookup between the two the user wil be presented with a picklist of PartsCategory that will fill with the SF generated, to the user meaningless, IDs. Obviously i would like to change this to Category(Plastics/Protection, Wheels.... etc.). What's the best way of doing this. I'm aware and have already create custom formula fields that display the Category and Location fields but how would i create/change the picklist so that the user can search/select on Category name instead of a meaningless Category ID ?

I have a similar question with picklists, it's important to us to seperate name/value pairs to be able to interact with other systems with existing IDs. Also, having hardcoded strings instead of name/value pairs like with picklists seems a bad idea to me altough from the research i've done there is not a clear and simple way how to handle these problems. To summarize:

1) What's the best way to implement name/value pairs for picklists ? (custom object with a lookup relationship brings me to the next question)
2) What's the best way to customize the field on wich a lookup relationships searches (so not on SF name field but say the CategoryName field)