I ended up using the BFG Repo Cleaner on a bare cloned repository (git clone --mirror repo-url). It goes through every branch/tag, leaving each working and it is even much faster than filter-branch. Hope this helps other people having similar issues.
Here is my wrapper script:
#!/bin/bash
#usage: ./remove_files.sh file_list.txt bare-repo-dir
while read file_hash file_to_remove
do
echo "Removing "$file_to_remove;
lastFile=`echo $file_to_remove | awk -F/ '{print $NF}'`;
java -jar bfg.jar --delete-files $lastFile $2;
done < $1
cd $2;
git gc --prune=now --aggressive;
cd ..;