Hi,
Try looking in Lunenburg County, Nova Scotia. Mailman is just an Anglicized form of Mehlman, which is German in descent. Most of the people in Nova Scotia of German heritage, settled in Lunenburg County.
I have quite a few Mailman/Mehlman's in my tree, my great grandmother being one of them, and they lived in Lunenburg County.
Vanessa