Looking at the records you mentioned, could the following provide any clues?
Since the earliest census stated that Norman was born in Vermont and his citizenship record shows Rutland County, Vermont I might guess that his actual birthplace was Vermont.
He was noted as being 6' 1" (citizenship record) which could have been an unusual height for that time? Have you looked at any Ames records to see if there were any possible siblings for Norman (who also might have been seamen and possibly taller than average)? Could Norman have been buried with Ames family members?
The notation for Beechinor/Ames Calvary Cemetery record on FindAGrave states that the plot contains 19 burials. You most likely tried contacting the cemetery office to see if Norman was buried in the cemetery?
https://www.findagrave.com/memorial/148272116Note: According to internet information from 2013, there is apparently a (somewhat large) fee to provide information. Also, since you don't know when or where Norman died, they most likely cannot help you. So, scratch that idea!
Is this a different Mary Ames?
1880 New York City Census
Presbyterian Hospital
Mary Ames, age 47, Boarder. Widowed/Divorced column is marked.
Born in Ireland as were parents.
Occupation: None
Sickness/disability: Intermittent(?) fever
I just found the Schedule of Defective, etc. and it appears to be the same person as noted above so if she was recorded accurately, she was widowed/divorced by 1880.
Since you've not yet found an obituary record for Norman, I wonder if he and Mary split up at some point? It seems a bit odd that you've found other newspaper bits but nothing for Norman.