assuming that you have something in your hands, getting a cad model from your positive is a good idea and either a cmm, laser scanner, portable cmm, or a probe mounted to a machining center is required. have them export the file in both .stl and .iges formats. ask for wireframe and solids output. most shops should be able to handle these files. on the left coast pricing for that might be in the $500 to $1500 range (using a cmm) depending upon your accuracy requirements and complexity of the part. or you could find somebody to wing it with cad software.
as far as searching goes, whenever i have to look for a vendor i start here:
http://www.thomasnet.com/
unfortunately when i went there, their site was locked up. i was going to look for shops in the mn area for you. i think the search term "prototype" best suites your case. if you are looking for a shop to generate a cad model for your part a "cmm" shop or "inspection" or "reverse engineering" would be where i'd start with terminology.
the way the mfg. world works these days is that if you want a part that isn't hand made, it's somehow gotta get into a computer. another old school alternative is to have the thing cast, but that doesn't really give you machinable data to work with. on the other hand a lot of this depends upon how complex the component is.
wish i could run the thing through our shop but unfortunately only national labs with phase 2 grant money can afford us.
