Entity Filtering mechanism
Customized as it may be, it worked:

Using VBO and performing a hook_form_alter onto the exposed filter form I was able to add a hidden field.

Using javascript, I store the values of the selected entities (derived from the checkboxes attributes) into the hidden field. If the user triggers the exposed form submission, the values remain and on the new page load I use the same values to recheck the checkboxes thus providing the illusion that the values got preserved.

Downside is the unavoidable use of javascript and the possible huge URL.

If anyone has anything better to propose or make the exposed form NOT place it's parameters as $_GET parameters in the url I'd be glad :)