There are actually many cheaper options in Probolinggo than the ones visible on internet or in lonely planet Indonesia (edition 2013).
I stayed in a guesthouse for 80'000 IDR per night, for a double bedroom with shower (cold water only). It was clean, not far from the train station, and staff was nice. The guesthouse is called "female guesthouse", although I'm a male, this name made no difference. Note that I went with my girlfriend.
I also found another few places with higher standards (i.e. With swimming pool for around 200'000 IDR).
Please find below a picture of a flyer from 2015 with different hotels and the relevant prices, address, phone number, and so on.
For further info, contact the tourism information office in Probolinggo, they were very helpful when I got in touch with them.