It seems AV1 allows to rotate reference blocks in inter prediction. I wonder what an algorithm that would search for a prediction MV would look like (not even counting bidir).

Even without rotation, MV search can get sophisticated and not exactly intuitive in a typical encoder. And with HEVC having "merge" that win that much bits, it's not like there was so much bits left to earn with the predictor itself.