I want to say that the New York PAID in black struck on a stamped cover is pretty unusual.
Normally these types of PAID markings, often along with a rate at the bottom -- which may or may not be present on yours -- are for foreign mail, and when pre-paid, are struck in red, reflecting a credit to a foreign country.
Black usually signifies unpaid, and, therefore, at least for foreign mail, does not have a PAID in it.
I did recently come across a black NY PAID with no rate (similar to yours) on a cover addressed domestically, of unknown origin. From memory, I want to say Chase or Ashbrook had stipulated that that cover probably originated in some foreign country and was deposited in the mail in the US, and the PAID applied to US domestic postage. That cover was franked with a single 3c 1857 stamp.
Yours may be a similar situation, with a domestic destination.
Nice stamps too
edit: To clarify, PAID in general for domestic usages is fine, and normal. I'm speaking specifically about this type and configuration of device used in NYC.