Block always cached for anonymous users

I have a custom module that displays a random fact from a db in a block. The block is set to show on the front page only. I have caching set to normal and block caching turned off. $blocks[0]['cache'] is set to BLOCK_NO_CACHE in hook_block('list'). $block['cache'] is also to BLOCK_NO_CACHE in hook_block('view'). The db entries for the block show caching for the block turned off. But the block is always cached. I can confirm this in two ways - 1) The expected db query doesn't fire as evidenced in phpMyAdmin and 2) any output added to hook_block() does not render. The block code just doesn't execute.

However, if I change the display option to show on all pages, the output changes for different paths. But if I return to a path I've already been to, the block output is the same as the first time I accessed that path.

If I'm logged in as user 1 (administrator) the block content changes as expected. I suppose that's because caching is ignored when user 1 is logged in.

I've tried every combination of cache setting, clearing cache, and reinstalling the module. Nothing seems to help.

Any suggestions would be appreciated.