"pdftohtml" seems to generate RTL text backwards. It's like (abc) is generated (cba). You can read the generated text from LTR but that's not convenient ;)
"pdftotext" is behaving correctly.
I'm seeing the same issue with poppler-utils 0.12.4 (Ubuntu 10.04.1).
Workaround for Hebrew: convert with "-enc ISO-8859-8". However, that discards all non-Hebrew Unicode characters (such as those used in math).
Simply reversing the Hebrew words in the output doesn't help, since the order of words in a sentence is also backwards.