I have learned to hate the Medallion Stamp BS. :
I use my credit union for this and have had only a few issues with doing it...mostly the branch manager is the only one allowed to do it. She knows me pretty well by now so I have no problems now. Since I carry over 6 accounts there with various subaccounts they tend to show a little more customer service than they used to.
I went the major bank and financial institution route for the stamp and it was usually "what is your account number? Oh, you don't have an account with us..I'm sorry this is a service only for bank customers."
The only difference I have seen between a Notary and a Medallion stamp is the higher quality of BS with the Medlallion stamp process. The same IDs are allowed by both but since an "institution" rather than an "individual" approve of who you are, the institution has more credibility and this gives financial institutions more trust in the correct ownership of whatever is getting the Medallion treatment. Don't like it....but what else are you going to do?