In the case of Tesco, the shares may be held by their Corporate Sponsored Nominee (CSN) which is Equniti's ShareView service. All shares held through a CSN appear on the official shareholder's register as owned by the CSN and they keep track of the real owners (see Equiniti's Coporate Sponsored Nominee page).
If your father's shares are in the Equiniti/ShareView CSN, then their Manage an Estate page may be of use. Note: If this is the case, registering your father's death with Equiniti using a Grant of Representation (Probate) will be considerably cheaper than using their Small Estate Service.
(Disclaimer: I have no connection with Equniti other than having had to deal with them a few years ago in connection with my parents' estates).
In the case of BP, according to this PDF document (linked from BP's Manage your Shares page) it appears Capita Asset Services provide the equivalent service – contact details for them are at the top of the PDF. The document also notes that Equiniti provided the service prior to October 2012.