Theming two instances of an input field in one form
Is there a reason having the class on the input would be better than having it on the block? e.g. does it make some CSS/JS awkward by not being able to target the input directly? 

If not, having the class on the block seems like the ideal solution both in terms of ease-of-development and semantics...you want the search input to be styled based on where it is. That feels like a natural separation for a hierarchy of selectors: .block .input

If the blocks are in different regions, you could use the region class instead, which is there by default in most themes; that would avoid even having to alter the blocks themselves.