¿Cómo podemos hacer eso con guayaba? Note la presencia deList<K> en el tipo de retorno ya que muchas claves pueden mapearse al mismo valor en cualquier mapa normal.

public static <K, V> Map<V, List<K>> inverse(Map<K, V> map){
    Map<V, List<K>> result = new LinkedHashMap<V, List<K>>();
    for (Map.Entry<K, V> entry : map.entrySet()) {
        if(!result.containsKey(entry.getValue())){
            result.put(entry.getValue(), new ArrayList<K>());                
        }
        result.get(entry.getValue()).add(entry.getKey());
    }        
    return result;        
}

BiMap Parece insistir en la unicidad de los valores, pero no tengo este lujo.