There are three types of compound nouns.
open or spaced - space between words (tennis shoe)
hyphenated - hyphen between words (six-pack)
closed or solid - no space or hyphen between words (bedroom)
Even though Wikipedia posted voice mail as a closed compound noun (still voice mail system is an open compound noun there) and you get more google hits for voicemail (18.1 million) than voice mail (9.9 million), this Ngram Viewer favors voice mail over voicemail. Also, another Ngram Viewer records more of voice mailbox or voice mail box than voicemail box.
As the two Ngram Viewers show, people started to use the words around year 1980 and as commented above, it is difficult to say which is correct. But, voice mailbox is the one which is favored.