When I log out, all my blocks disappear

I've been scouring forums for almost two hours but to no avail so far.

I have a fresh installation of Drupal 6.12 installed from custom profile with a custom theme. I've downloaded several other themes for testing and also created several items to primary and secondary links. Everything was OK and after some toying I wanted to look at the web while logged out - then I saw all of the blocks gone, only logo and content of frontpage remained.

I've triple checked that the blocks are enabled, that the themes have default link blocks enabled (in global settings as well) and that all blocks have correct visibility settings (by default none role was selected which should mean no restrictions but I tried to check all roles as an alternative setting with the same effect - didn't work). I didn't find anything that would prevent blocks from appearing in admin/user/permissions - anonymous users can access and search content.

Then I disabled all testing themes and activated only bluemarine - still nothing, upon logout all blocks disappear. I even have another testbed installation on another server where everything is default, but even there items in primary links disappear upon logout while login block and Recent posts block remain...

This must be something mundane but I don't really know what else to check. Thanks in advance for hints.