I work on a system that has similar requirements - partners drop files that contain anywhere from 10 - 1,000,000 records to be processed. Some partners drop the files once a day, some once an hour, and others are ad-hoc.
Our system uses a data integration tool at its edge to validate the file, breakup into (up to) 1000 record batches, transform each batch into a normalized JSON payload (different partners can have different data formats), and send to REST endpoint of an orchestration service. Internally, the orchestration service is multi-threaded so that batches are processed in parallel. The orchestration service returns a response that includes a status for each record in the batch, and the data integration tool is smart enough to, for each record, record success, schedule the record for retry, or route the record to a terminal failure bucket.
All of the critical services used by the orchestration service are synchronous, but there is some use of messaging for non-critical processing. This approach works well for us.
Addressing some of your concerns:
First, you say REST is not as scalable as messaging. I think you're alluding to the fact that HTTP creates a connection per request, whereas message brokers typically keep connections open to avoid the setup/teardown overhead. That is the reason we send the records in batches - to amortize that overhead over many records. If you are going to use messaging, there may not be enough benefit to batching to warrant the extra complexity of processing batches.
You mention that taking an all or nothing approach to batch success/failure could clog the system. We agreed, that is why we designed our system so that "good" and "terminal failure" records are only processed once - only records that suffered some form of transient error are retried. Arguably, this logic is easier to implement with all of the critical processing being synchronous, rather than trying to keep track of all of the "in-flight" records being processed asynchronously.
Finally, you mention that records that are retried my have issues because some services have been updated while the records were waiting to be retired. That is an entirely separate issue. If your system has the possibility of that happening, then you must version your services so that an update allows records partially processed by an old version of the overall process can complete using the correct versions of the remaining services. Only after all of the data has flowed through the system and old version is no longer needed is it removed. We have a versioning policy that prohibits making breaking changes to an API, if breaking changes are required, a new version of the API is created and that old version is only removed after we know that all clients have been updated to the new version.
Hope this helps...