We had a public site that has a lot of Content Search web parts, everything was working fine but suddenly search web parts stopped working only for anonymous users and was working fine for logged in users.

After some Googling and full crawling, I managed to get it working using the following PowerShell Script, I had run it for every list and library that search read data from

#Add-PSSnapin microsoft.sharepoint.powershell
cls
 $web = get-spweb "http://your server"
 $web
$list = $web.Lists["List Title"]
$list
$list.BreakRoleInheritance($true)

$list.AnonymousPermMask = $list.AnonymousPermMask -bor ([int][Microsoft.SharePoint.SPBasePermissions]::ViewFormPages) #binary or adding the permissions

$list.Update()