Why is this spirit giving positive witness to Paul's claims?
Frank Luke has some intriguing arguments that her witness was flawed. However, it would seem odd if this were a sort of pluralism; would the way of salvation not have been unique to Christian theology? In other words, even if the phrase has some grammatical indefiniteness, I find it difficult to belief that the idea of ὁδὸν σωτηρίας, "way of salvation," was anything but distinctively Christian.
Whether she said this of her own accord, or was obliged to it by divine impulse; and whether it was through fear of Paul, and in flattery to him, or was with a good or bad design, is not easy to determine: however, certain it is, what she said was truth; and sometimes the devil himself, the father of lies, is obliged to speak it.
Henry likewise takes the testimony to be true, and suggests that either the spirit was constrained by God thus to witness, or that the Devil was contriving to disgrace the apostles, "as if these divines were of the same fraternity with their diviners."
If it is true testimony, why does Paul eventually get annoyed?
Paul was not angry with the girl, but with the spirit that was oppressing her. See Swasheck's answer with regard to this. Frank Luke also has some good, relevant discussion. Gill's reasoning overlaps with both these answers:
Paul being grieved at the unhappy condition the maid was in...and that the people were so imposed upon and deluded by it; and that it should be thought that there was any combination and agreement between that and him.
Henry also takes it to mean that Paul was grieved to see Satan working through her. He also suggests that she may have been shouting these words in a mocking way, similar to "Hail! King of the Jews!" which seems quite plausible.
There's an additional point that may be helpful. The example of Christ is already to cast out the demons, even when they give a positive witness.
In the synagogue there was a man possessed by a demon, an evil spirit. He cried out at the top of his voice, “Ha! What do you want with us, Jesus of Nazareth? Have you come to destroy us? I know who you are—the Holy One of God!”
“Be quiet!” Jesus said sternly. “Come out of him!” Then the demon threw the man down before them all and came out without injuring him. —Luke 4:33-35 NIV
Again, he didn't renege after a positive testimony:
He shouted at the top of his voice, “What do you want with me, Jesus, Son of the Most High God? Swear to God that you won’t torture me!” For Jesus had said to him, “Come out of this man, you evil spirit!” ...The demons begged Jesus, “Send us among the pigs; allow us to go into them.” He gave them permission. —Mark 5:7-8, 12-13
No allegiance is to be had with the Devil even when he is apparently giving help! The power of God is enough.
Why didn't he perform the exorcism immediately?
Gill says that Paul delayed in order to make the eventual expulsion more emphatic and noticeable. Henry suggests it was because Paul for a time thought it was a providence to aid him, and only cast the demon out once it became a hindrance. This seems to conflict with the point made above, however. This question is perhaps the most difficult; I commend Frank Luke's suggestions on it.