I have tried to reproduce this under Plesk 11.5 (the original problem appeared in Plesk 11.0) on CentOS 6.4 as we have upgraded all our servers since posting this problem.

I think the original problem might have been linked to updates rather than reboot as these occur concurrently. After updating Plesk Panel and doing yum updates (including kernel updates) we would reboot the server and experience the lost greylist cache problem.

I could not reproduce this on Plesk 11.5, so could it have been a problem under Plesk 11.0 while applying micro updates?

It should not happen on server reboot so i was trying to investigate the problem.
I've been checking this problem on our local environment and see no problem on reboot.
GL is turned on
sent email from external host(message has been rejected)
waited until GL interval has been expired
sent again (message passed and GL added sender information into DB)

GreyListing stores sender information in /var/lib/plesk/mail/greylist/data.db:
select * from data;
remoteIP|mailFrom|rcptTo|blockedCount|passCount|creationTime|lastUpdate|greyExpires
10.10.10.10|66sx@domaintz86.com|34ia@hostname.tld|0|3|1383719678|1383719819|1383719798
10.10.10.10|68un@domaincr41.com|34ia@hostname.tld|0|5|1383719912|1383720053|1383720032
10.10.10.10|07ge@domainki75.com|34ia@hostname.tld|0|5|1383720675|1383721027|1383720795
10.10.10.10|52zm@domainws39.com|34ia@hostname.tld|0|6|1383721203|1383721488|1383721323

and after server reboot all records still exist and me messages still can be delivered w/o problems...
May be smth i'm doing wrong way in my attempt to reproduce. Can you indicate exact steps to reproduce the issue?

I have the same problem. After each upgrade the messages are delivered with a delay. In my opinion, this is so obvious, I'd even consider this as a bug.