Sorry for posting this as an answer, I am not sure if this is actually an answer. But I can't comment yet, anyway.
I see two different problems here. First, whether the ascending order should be represented by a triangle pointing up or down (or similar icons). Second, whether this icon represents the current (now) or the future state (after click).
As for ...
The new record should be added based on the sort order selected. Even if that means that the new record won't be visible on the currently selected page. This is to ensure that the data presented it correct and avoids making it look like your application has a potential issue with sorting.
The obvious concern with this approach is that the user might not ...
I would add somewhere an async counter that shows the amount of downloaded data and total amount of them that's left e.g.
Gathered data from 23 providers of 150 total
Querying for data:
23 / 150
(search results may live update once data is downloaded)
The text content might be different, but wanted to illustrate the main idea.