Are there other cheeses which have similar properties to halloumi, like the fact that it doesn't melt easily and can be grilled, fried or barbequed?
Paneer (Indian cottage cheese) doesn't really melt and is often fried. Other cottage cheeses, and I suspect cheeses made with low-fat dairy, will have high melting points.
Yogurt-based cheeses (feta) don't melt much, but don't have a lot of structural integrity either.
The Wikipedia article above linked to farmer cheese, which linked to Queso Blanco, which is a Mexican farmer cheese that is also resistant to melting (although apparently there are different types that do melt). Flavor is sorta similar to halloumi, although I've only had one brand and flavors probably vary.