Of course the proper solution will be for Google to fix the problem (see Android Maps V2 issue 4639: http://code.google.com/p/gmaps-api-issues/issues/detail?id=4639).
However, one of my coworkers suggested simply extending the map beyond its container. If we extend the map fragment beyond the visible region of its container, like so:
android:layout_marginLeft="-40dp"
android:layout_marginRight="-40dp"
we can reduce/eliminate the flickering. Newer devices (e.g. Galaxy Nexus) show no flickering after this hack, and older devices (e.g. LG Optimus V) show reduced flickering. We have to extend margins on both sides so that info windows are centered when they’re selected.
Update: This issue was fixed by Google on Aug. 28, but I’m guessing it still has to be rolled into a release.