Set custom order status for complete PayPal Website Payments Standard payment?

The big problem is, there is not even a single event in the whole paypal work flow.

So there are two options:

Rewrite any of these Paypal models

As you said, just rewrite the model, change the behavior and everything works as expected - hopefully or...

Hook into sales_order_save_before

Then you check for the payment type, which should be \Mage_Paypal_Model_Standard::$_code with:

protected $_code  = Mage_Paypal_Model_Config::METHOD_WPS;

\Mage_Paypal_Model_Config
-> const METHOD_WPS         = 'paypal_standard';

And then, when the status is changed to the one you don't want, change it to the one you want.