So I'm writing my formatter to actually make use of the provided TermInfo characteristics of the connection, instead of just assuming that it was ANSI compliant. And all has gone fairly well. The code is unit tested, and I know it works. So I plugged it in, and connected to the server using telnet. And the initial menu was missing formatting that it had before.
I tried changing terminal types a couple of times, in case the terminfo data was wrong. I tried a few other things. I then randomly hit enter on the menu, which causes the menu to re-render. And this time, the rendered menu had the formatting.
So I fired up Wireshark and watched. It turns out, the menu is initially sent before the Terminal Type option response is received, so when it is first rendered we have no details about the terminal type, and so assume that formatting isn't possible. It's technically wrong, but it's safe. And I'm happier with safe than I would be with spewing garbage on the screens.