Используя awk, найденное решение:
awk 'BEGIN{FS=":|,";i=0;}
/reqCompleted/ || /reqId/{
arr[$i]=$2;
lines[$i]=$0;
i++;
}END{
for(key in arr){
if(arr[key] in arr){
}else{
print lines[key]
};
}
}' input.txt
Это дает ожидаемый результат как:
2016-09-27 reqCompleted: 000-pat1-bgr, more characters
2016-09-27 GET /some/uri - reqId: 0.215487, your favourite song
2016-09-27 reqCompleted: 0.215487, more characters
2016-09-27 GET /some/uri - reqId: 000-pat1-bgr, more text