How to vertically middle-align floating elements of unknown heights?

You can’t do this directly, because floats are aligned to the top:

If there is a line box, the outer top of the floated box is aligned
with the top of the current line box.

The exact rules say (emphasis mine):

4. A floating box’s outer top may not be higher than the top of its containing block.
5. The outer top of a floating box may not be higher than the outer top of any block or floated box generated by an
   element earlier in the source document.
6. The outer top of an element’s floating box may not be higher than the top of any line-box containing a box generated by an
   element earlier in the source document.

8. A floating box must be placed as high as possible.

That said, you can take advantage of rule #4:

• Place each float inside inline-level elements that establish a new block formatting context /BFC), e.g. display: inline-block.
• These wrappers will contain the floats because they establish a BFC, and will be one next to the other because they are inline-level.
• Use vertical-align to align these wrapper vertically.

Be aware that some space might appear between the inline-block wrappers. See How to remove the space between inline-block elements? to fix it.

.float-left {
  float: left;
}

.float-right {
  float: right;
}

#main {
  border: 1px solid blue;
  margin: 0 auto;
  width: 500px;
}

/* Float wrappers */
#main > div {
  display: inline-block;
  vertical-align: middle;
  width: 50%;
}

<div id="main">
  <div>
    <div class="float-left">
      <p>AAA</p>
    </div>
  </div>
  <div>
    <div class="float-right">
      <p>BBB</p>
      <p>BBB</p>
    </div>
  </div>
</div>