Comparison of alkali and alkaline earth melting points - MO theory
From "The Nature of the Interatomic Forces in Metals" by Linus Pauling


  This qualitative description of the interactions
  in the metal is compatible with quantum mechanical treatments which have been given the
  of
  problem, and it leads to an understanding
  such properties as the ratio of about 1. 5 of
  crystal energy of alkali metals to bond energy of
  their diatomic molecules (the increase being the
  contribution of the resonance energy), and the
  increase in interatomic distance by about 15
  percent from the diatomic molecule to the
  crystal.
  The alkaline earth metals, by assuming the
  configuration nsnp, are able to form twice as
  many bonds as the alkalis. Similarly the suc-
  ceeding elements in the periodic table can form
  bonds in increasing number.


You are right on the fact that alkaline earth metals should not bond if we only considered their highest atomic energy levels. The dissociation energy for diatomic clusters of alkaline earth metals is low.

However, the disassociation energy gets higher for tetra-atomic as shown in this computational study: http://www.sciencedirect.com/science/article/pii/0039602885902328

Now, the reason why alkaline earth metals have higher melting points to be due to the p orbitals. The previous study relates p hybridization with bond strength. And so does this study: http://scitation.aip.org/content/aip/journal/jcp/77/8/10.1063/1.444313

Both journals state that p orbitals are involved in bonding. And the more involved the p orbitals in bonding, the stronger the bond. This trend is shown for alkaline earth metals. Beryllium, which has the highest melting point, also has more p orbital character. Also, take a look at the density of states of alkali metals and alkaline earth metals:
http://www.colorado.edu/engineering/MCEN/MCEN5024/

You can see that not all p orbitals are entirely above the s orbitals.

So, to answer your question. The reason why alkaline earth metals have higher melting points is due to p orbitals. As Pauli states in his review, the np orbitals "hybridize" with the s orbitals. This allows for more bonds to form.

I think that p orbitals participate in bonding in alkali metals. But I couldn't find information that compares p orbital "hybridization" of alkali and alkaline earth metals directly.