According to Article 6 of Convention of 5 October 1961 Abolishing the Requirement of Legalisation for Foreign Public Documents there is a official and updated list of authorities who are competent to issue the certificate. On the official website
hcch.net you can find and filter
Authorities per state or per convention, filtered per Convention of 5 October 1961 will list all authorities sorted by country worldwide.
According to Article 7 of Convention of 5 October 1961 Abolishing the Requirement of Legalisation for Foreign Public Documents:
Each of the authorities designated in accordance with Article 6 shall keep a register or card index in which it shall record the certificates issued, specifying the number and date of the certificate, the name of the person signing the public document and the capacity in which he has acted, or in the case of unsigned documents, the name of the authority which has affixed the seal or stamp. At the request of any interested person, the authority which has issued the certificate shall verify whether the particulars in the certificate correspond with those in the register or card index.
It does not say anything about rules, fees, if they have to provide this service free over phone, it depends, some countries have only personal or phone verification, some allow e-mails, some have e-Registry and some issue even e-Apostilles signed digitally.
When trying to find an online verification form, it helps to look for e-Register, that is what it is called in most of US states that support it, UK, Ireland, New Zealand ... and many others, according to question 12 in official HCCH's guide ABCs of Apostilles:
Many Competent Authorities have started to operate online electronic Registers (e-Registers). These e-Registers allow for easy online queries to verify the origin of an Apostille without Competent Authorities having to answer these queries individually by phone, e-mail or otherwise. If a Competent Authority operates such an e-Register, the web address of the e-register is mentioned on the Apostille.
My first encounter with notary fraud inspired me to ask this question. My research is in progress and I found out, that this part of question is too broad to be answered here. As it is easy to find notary on the internet, and his name and commission number, I am failing to find guides and regulations on their duty to cooperate when I want to confirm his records with document I have in hand. It varies from state to state in US, country to country worldwide. Usually there is no reference to fees for record verification, deadlines, anything useful in process of verification. There are many documents like Prohibited Acts, Duties of a Notary Public, Notary Public Handbook, but I do not find them useful as a source for somebody who wants to verify if notary is a fraud. I found on several .gov websites with some US states, that notary public is not obliged to keep records. To somebody paranoid and with trust issues, choice is to either ask your international clients for Apostille or to use notary you trust, that is not always possible.