I'm a notary in the state of Vermont, USA. I personally believe I can use common sense when it comes to using a passport or similar document to identify a person who is about to sign a document that needs to be notarized. But there are some notaries who believe in a mythical "more but not less" rule. They think that if the name on the document is ...
Would these stamps always be given on request (e.g., for Americans who want to prove that they did not overstay in a foreign country)?
No, according to https://stuff.mit.edu/people/stransky/us_entry_passport_stamps.html (mirror):
Ports of entry I've used with no stamp received, even after asking:
San Ysidro, California
El Paso, Texas