I figured an update might be in order here. One of AA Wireless's many, many configuration options is the ability to put the AA Wireless box to sleep when the car turns off. This should probably be the default setting. Enabling this "sleep" feature seems to mean that my phone isn't trying and failing to connect to the AA Wireless box when I'm outside the car, and that seems to keep everything in the proper state so I'm now back to a situation where everything "just works".

FWIW, I spend a non-trivial amount of time in rental cars these days, and Android Auto support typically just works without any issue. I'll jack into the USB port, connect the phone, and it displays. It's not entirely clear if/when a given car supports wireless Android Auto. When it works, the pairing you set up with a cable sticks around. But it doesn't always work.