I'm missing a feature to let OllyDbg automatically do repetive stuff, like "Search for binary string 'xyz' and replace it with 'zyx'" or "Search and set Conditional BP on each occurrence".

I haven't looked into the Plugin SDK -- would it be possible to implement this functionality in a Plugin?

Cvx: yes it is possible, check cmdline plugin by Olly for more information