Custom block displayed via Contexts not being shown to anonymous users
I found the source of the problem. 

I had used hook_block to create the block. I had specified BLOCK_CACHE_GLOBAL for the cache settings of the block which means the blocks were cached the same way irrespective of the page or the user. 

I changed the cache setting to BLOCK_CACHE_PER_PAGE and it solved the problem. (The block hosted an openx ad which was only displayed on pages with certain taxonomy terms.)