The thing to remember here is that npcs seem to be only able to act on a single action at a time.
(Ala - the Action Queue)
While they are 'walking' this is an action.
When you ask them to speak, that is another action - which goes to the bottom of the queue, or at best, behind the current action.
ClearAllActions will allow you to clear out the action queue and put something first in line to be acted upon, but it has the side effect of interrupting the walk action.
Eg: They may stop walking momentarily to deliver their SpeakString.
Im not sure - but I guess with this logic, even my earlier suggestion of using a trigger, would be at the mercy of the Action Queue.
The trigger would at most be able to add to the end or add a new action behind the current action.
ClearActions would be needed for trigger based scripting too.
It might be a little too complex for what is needed, but I am reasonably sure that nwnx would be able to get around this issue. (nwnx_chat ?)
Eg: It could send the chat message - using the NPC as the speaking object.
Because it is bypassing Action Queue - it would not require ClearActions
Since your not relying on the Creature actually speaking, instead its the server speaking, just changing the object ID to the creature.
So the creature would in effect be able to talk and walk at the same time.
At least, that is my theory