What cheeses work 'best' in melted cheese sandwich applications?
Gruyere is DELICIOUS. It melts without getting too gooey or soupy, and it is the traditional cheese component of a Croque Monsieur (if you're into that ham thing...). You could actually probably use any of the cheeses in that "variations" list, but I love Gruyere so that's my recommendation. It's widely available but tends to be kind of pricey here in the US.

Brie is also a good choice; since it is soft to begin with, it melts nicely. (Just make sure to cut off the rind before putting in the sandwich - that would be a weird texture combo.) It's great in grilled or toasted cheese sandwiches because of the richness and slightly buttery flavor.

As a local reference, check out Gorilla Cheese's menu for some tasty ideas; they do classic grilled cheeses with cheddar, American, gruyere or mozzarella, but they make others that have additions of other non-cheese components.