Powered down = turn car "off", then open the car door. This seems to cut power to most of the car's systems, e.g., turning off the stereo. I've let it sit overnight and will try again today. After some Google searching, it's also possible to hold down the power/volume knob for 10 seconds to force a reboot.
AA Wireless: if you have a car with USB Android Auto but not the newer Wireless Android Auto, this is one of the gadgets that's seen as a solid alternative. There's also a cheaper one from Motorola, which I originally had, but it flaked out and died.
Some additional background and then a few hypotheses:
The original Android Auto ran over USB. The idea was that your phone could take over the screen in your car. Also, there was some amount of extra metadata, like whether your headlights were on, as part of the protocol. At least with my car, one of the problems with this was that the physical USB connection became unreliable. I'd go over a bump and it would go blank for a second then reconnect.
The newer wireless variant is the solution. I don't entirely get how they managed this, but if you're in a car with wireless Android Auto, integrated from the factory, then the initial Bluetooth pairing process will (sometimes) also lead to a wireless Android Auto pairing. I believe it then uses local WiFi for moving the bulk data around. In other cases (rental cars are awesome), you do initial setup with a USB cable, and you get a Bluetooth pairing automatically. Subsequent times you get into the car, it's automatically using wireless Android Auto.
So, back to the AA Wireless box. They were originally an Indigogo solution to adding wireless Android Auto to cars, like my VW, which only had the wired version. Where the cheap Motorola adapter just does "pass thru" of the protocol, the AA Wireless software has a variety of toggles in it that explicitly work around bugs with different cars. So far as I can tell, it's the best solution to my problem, and it worked without issue, for years, until yesterday.
Anyway, enough background. I'm really curious about that error message I got on the screen in the car. "Pixel 9 / Unable to connect to mobile device. The device AA Wireless is already connected through Android Auto." When my AA Wireless is disconnected and yet I try to do a Bluetooth pairing, this still happens. The hypothesis I'm coming around to is that the VW headunit has some concept of Android Auto "overriding" Bluetooth from the same device, and it's gotten into a weird / buggy state where it can't recognize that the Android Auto connection ain't there. The test for this hypothesis is that I need to reset the head unit. Maybe that's just the ten-second press of the power button. Maybe that's disconnecting the battery. TBD.