Recursively replace string placeholders with parameterized phrases
What if you would use re.sub() with a replacement function until there are no unfulfilled placeholders left. Something along these lines:

PHRASE_PATTERN = re.compile(r"(bb:\w+)(?:\[(.*)\])?")

def expand_message(message):
    """Recursively replaces any occurrences of building blocks with its text."""
    while "bb:" in message:
        message = PHRASE_PATTERN.sub(lambda group: phrases[group[1]].format(*group[2].split(","))
                                                   if group[2] else phrases[group[1]],
                                     message)
    return message


This way you don't need to iterate over all the available phrases and only handling the phrases used in a message. Should scale much better.