I have been in an online chat with EverNote for some time with this issue. I now discovered the pattern.When you take an image in a note from within the iphone app, it appears correctly on the iphone. Then I sync with the PC of Mac client and it appears 90 dgrs rotated. These rotated shots are not searchable. When you first take the picture outside the iphone app and then add it to the note its orientation is ok. Why is it that no one else noticed this behaviour.
lossless jpeg rotation should be a rather simple and low CPU task. Plenty of implementations out there. I notice a lot of issues with this rotation thing, images apear differently rotated in the various EN clients. This also makes them non searchable!