There is much uncertainty in the literature about the structure of several Be-B phases between 20 and 33 atom % Be. We clarify the structural choices in this region of the phase diagram, proposing structural candidates obtained from a combination of chemical intuition and unbiased solid-state structure searches. In particular, we discuss the structural, dynamical, and electronic properties of the ground states of the BeB2, BeB3, and BeB4 phases, as well as those of the complex (and superconducting) "BeB2.75"phase. For the latter, we find the polyhedral borane cluster electron-counting approach very useful to explain its electronic structure. We can also make sense of the partial and mixed occupancies in the structure by looking at the cavities in a parent structure. A Be29B81 stoichiometry seems most reasonable for the ground state of this phase. The electronic structure points to a region of stability for three additional electrons per unit cell, a 1% difference in total electron count. For BeB2, which is usually studied computationally in the AlB2 structure type, we find several other structure types that are more stable, all essentially Zintl phases with 4-connected boron networks. New structure types are also predicted for BeB3 and BeB4 as well.