The following answer is based on my interpretation of US law relevant to this question as the reseller identified is a US based vendor and those laws would be applicable to them. Check the laws applicable to your country.
When I received the MacBook, it was in a 2016 refurbished Apple MacBook Pro box. (Even though the MacBook I received is a 2017 version).
To me, this sounds like it should be classified as either "open box" or "refurbished." The question is, how did they advertise it?
If they represented it as "new" and it showed up as you describe, that would be considered deceptive (15 USC § 45)1. If however, they stated it was "new OEM purchase" (new but not in retail packaging) or "new, open box" and clearly said so, more than likely it would pass as legit.
Companies can, in fact, take opened products and repackage them as new so long as there is a conspicuous process to validate that it is actually unused.2
On OWC's website (MacSales.com) they have a "new" listing for a Mac Pro in which they state "factory sealed."
Hypothetically speaking, if you purchased this computer and it showed up in a "refurbished box" as you describe, it could be considered deceptive. It boils down to how was it advertised and what you actually received.
I can ask Apple to check the serial number and see if its ever been registered with someone else other than me. Will that work?
It's a good step, but not conclusive.
In other words, it can be proof positive that it was used if there was a registration but alternatively, give you a false negative if it was used but never registered.
I checked the battery cycle, and its at 4. Is that substantial? (Do new Macs come with a battery cycle like that?)
No, that is not substantial at all.
It's not uncommon for vendors to charge their devices so that the "unboxing" experience" is a positive one which would include getting a device with a charge substantial enough for you to immediately use it. Remember, you're purchasing a 2017 model at the end of 2018 so, theoretically, it could have been sitting around for a year.
Buy from a trusted source, not the cheapest. If you are not comfortable with the deal you got and there's a lingering voice in your head questioning whether or not you were deceived, return it. The few extra dollars you're going to spend on that peace of mind will be well worth it.
To put this into perspective, I have the technical ability to tear down a Mac and actually replace components at the board level. I still wouldn't buy something advertised as "new" from a source I wasn't sure about. To me, it's not worth the time, money or hassle.
None of the above should be construed as legal advice. I am not a lawyer nor do I play one on TV.
1 15 U.S. Code § 45 - Unfair methods of competition unlawful; prevention by Commission
2 FTC Staff Advisory Opinion Offers Guidance on New Products