I used Impactor to perform this test. Impactor generates all of the packages it needs at runtime (it includes enough of the aapt machinery to compile its own manifest files). In order to work around some situations where packages get "wedged" on some devices, all of the packages it generates have a unique package identifier based on the current timestamp. The APK files I was installing are thereby always "never before seen" files.
(FWIW, it is my understanding that Verify Apps is part of Play Services, so updates to it can be pushed at any time to all devices: if they previously were just sending a SHA-1 of the entire APK to the server, and now needed to check if the file size divided by the current day was a mersenne prime, they could push an update to do that on the client. They thereby are not limited to only "inherently backward-looking" techniques for this protection.)
Thanks for the extra detail. It's good to see that Google is clearly doing more than just signature-style checks. I knew they could do that sort of thing in Play Services, but, based on past coverage/discussion I wasn't confident that they were.
That still leaves open the question of security issues that aren't well-known, of course. Thinking about it a bit more, I can see the attraction of not adding extra complexity to the Play Services verifier until they "had to". If they're doing server-side checks and analysis that include undisclosed/low-profile issues that could be a reasonable balance (even if there is some lag time involved for simulations and the like), but if they're not...
Sadly, we're unlikely to ever know the difference.
(FWIW, it is my understanding that Verify Apps is part of Play Services, so updates to it can be pushed at any time to all devices: if they previously were just sending a SHA-1 of the entire APK to the server, and now needed to check if the file size divided by the current day was a mersenne prime, they could push an update to do that on the client. They thereby are not limited to only "inherently backward-looking" techniques for this protection.)