I have the same issue. Changes get pushed to gerrit and rebased on the server. This is what I have, though not perfected yet.

  prunable = "!f() { \
  : git log ; \
  target=\"$1\"; \
  [ -z \"$target\" ] && target=$(git for-each-ref --format=\"%(refname:short)\" --count=1 refs/remotes/m/); \
  if [ -z \"$target\" ]; then echo \"No remote branches found in refs/remotes/m/\"; return 1; fi; \
  echo \"# git branch --merged shows merged if same commit ID only\" ;\
  echo \"# if rebased, git cherry can show branch HEAD is merged\"  ;\
  echo \"# git log grep will check latest commit subject only.  if amended, this status won't be accurate\" ;\
  echo \"# Comparing against $target...\"; \
  echo \"# git branch --merged:\"; \
  git branch --merged $target  ;\
  echo \" ,- git cherry\" ; \
  echo \" |  ,- git log grep latest message\"; \
  for branch in $(git for-each-ref --format='%(refname:short)' refs/heads/); do \
   if git cherry \"$target\" \"$branch\" | tail -n 1 | grep -q \"^-\"; then \
    cr=""; \
   else \
    cr=""; \
   fi ; \
   c=$(git rev-parse --short $branch) ; \
   subject=$(git log -1 --format=%s \"$branch\" | sed 's/[][(){}.^$\*+?|\\/]/\\\\&/g') ; \
   if git log --grep=\"^$subject$\" --oneline \"$target\" | grep -q .; then \
    printf \"$cr  $c %-20s $subject\\n\"  $branch; \
   else \
    printf \"$cr  \\033[0;33m$c \\033[0;32m%-20s\\033[0m $subject\\n\"  $branch; \
   fi; \
  done; \
  }; f"

It prints the results of 3 methods:

1. git branch --merged

2. git cherry

3. grep upstream git log for a commit with the same commit subject

Has some caveats, like if upstream's commit was amended or the actual code change is different, it can have a false positive, or if there are multiple commits on your local branch, only the top commit is checked

if you're using gerrit then you have the Change-Id trailer you can match against?