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
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
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:
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.