At the Renaissance fair a few years back I was watching a smith forge metal into shapes. During this time a very odd question came to me. I was wondering what the furnace was made of. My logic stated that whatever the furnace was made of must have a higher melting point than the materials he was melting. This quickly turned into an elemental arms race resulting in an odd question of how do we melt stuff like refractory metals (more specifically the one with the highest melting point) so we can melt other things inside of it. 

Now I know that (for some odd reason I don't understand) rapid cooling can manipulate the strength of an item. Is there a similar property to manipulate the melting point? 

Note: My current best guess (like can be done to make weapons harder) is that we take two elements, melt them, and the resulting compound has a higher melting point.

Tungsten's melting point of 3422 °C is the highest of all metals and second only to carbon's, for which melting occurs only at high pressure (there's no standard melting point). This is why tungsten is used in rocket nozzles and reactor linings.  There are refractory ceramics and alloys that have higher melting points, notably $\ce{Ta4HfC5}$ with a melting point of 4215 °C, hafnium carbide at 3900 °C and tantalum carbide at 3800 °C.
Carbon cannot be used to hold molten tungsten because they will react to form tungsten carbide.  Sometimes ladles and crucibles used to prepare or transport high melting point materials like tungsten are lined with the various higher melting ceramics or alloys.  More typically tungsten and other refractory materials are fabricated in a non-molten state.  A process known as powder metallurgy is used.  This process uses 4 basic steps:

powder manufacture - a variety of techniques are available to generate small particles of the material being worked
powder blending - routine procedures are used to blend the constituent particles into a uniform mixture
compacting - the blended powder is placed in a mold and subjected to high pressure
sintering - the compacted material is subjected to high temperature and some level of bonding occurs between particles.

