It does not sound this bad.
A cronjob is a good start. Instead of triggering a second script, you can do the processing as part of the cronjob.
The easiest is to limit the number of processed messages low enough, that it is finished before it is run the next time. Running it every 5min should be often enough for most cases.
If the limit is not possible, because it sometimes needs more time, or because you need to process as much messages as possible in one run, you can use some kind of locking mechanism.
[UPDATE]
ok, as I now know more about the scope, we need to think a bit bigger.
As you need a guarantee for messages to be processed you will need a queue system. This can be RabbitMQ(which is the most stable and tested solution), this can also be Kafka(probably no, this is really to much), or my favorit as a first step, a simple queue table which consinsts of only the necessary collums. (mysql scales quite well in general)
The reason is, you must be able to split "accepting new messages" from processing them. The processing must be able to fail, without loosing the initiating message, so you are able to retry.
From experience I know, that some "requests" will need far more then just a few seconds to process, but you should be able to accept new requests from other users while processing a request.
Also, some Shops may want to scale the process up, because they have such a big audience, that a few 100 requests per minutes are not unlikely. Having a proper queue system allows to scale the processing part up.
This means, you should also use an additional queue to schedule the results for sending out.
Because the accepting/sending part is very hard to scale higher then 1 worker per chatservice.