Must compounds formed between solids be a solid as well?
No, they don't have to. In short, you have to memorize. The physical state of a compound has nothing to do with the states of its elements.

Examples:
$$\ce{Hg~(liquid) + Br2~(liquid) -&gt; HgBr2~(solid)}$$
$$\ce{C~(solid) + S~(solid) -&gt; CS2~(liquid)}$$

Now, there are some common patterns (an ionic compound is most certainly a solid; a compound with small non-polar molecules is probably a gas), but that's another story.