En la nueva API de Google Maps para Android, podemosagregar un marcador, pero no hay manera de (fácilmente) eliminar uno.

Mi solución es mantener los marcadores en un mapa y volver a dibujarlos cuando quiero eliminar un marcador, pero no es muy eficiente.

private final Map<String, MarkerOptions> mMarkers = new ConcurrentHashMap<String, MarkerOptions>();

private void add(String name, LatLng ll) {
  final MarkerOptions marker = new MarkerOptions().position(ll).title(name);
  mMarkers.put(name, marker);

  runOnUiThread(new Runnable() {
    @Override
    public void run() {
      mMap.addMarker(marker);
    }
  });
}

private void remove(String name) {
  mMarkers.remove(name);

  runOnUiThread(new Runnable() {
    @Override
    public void run() {
      mMap.clear();

      for (MarkerOptions item : mMarkers.values()) {
        mMap.addMarker(item);
      }
    }
  });
}

¿Alguien tiene una idea mejor?