In a genuine probate case the executor of the estate will not ask beneficiaries for money. The executor has a duty to identify the beneficiaries of the will and notify them, usually before the will is probated.
There is the possibility, however, that the will has been probated and the beneficiary has not been found or the person died intestate. In this situation, there are people who will try to broker the situation by making guesses who the beneficiary might be. These people are called "heir hunters". That might be the situation here.
However, just because the estate is real doesn't mean you are the beneficiary. It is possible that the fee hunter just mailed everyone with the same name of the missing beneficiary, which could be 100 people. Maybe one of them is the true beneficiary, maybe none of them are. If you pay him $500, he will probably just refer you to the executor. In the slight chance that you are the real beneficiary, then it is your lucky day. It is far more likely that you have no relation to the deceased and the executor will determine that and inform you.
If you want to pursue the case, you can start searching through unclaimed inheritance databases. Two of the provinces, Alberta and Quebec, have a comprehensive consolidated database of unclaimed inheritances. Unfortunately, the other provinces are harder to research, but there is a guide to how to do it.
In all probability, however, you are not the heir. If you were definitely the heir, the heir hunter would have given you a much more personalized letter and would have demanded more money, as much as 20% of the inheritance. Since he only asked for $500 it means it is probably just a random name match and nothing more.