An army would not go around re-building castles broken down by comrades. That army would fall. Casting out devils (for real), including healing of mind and body, is like rebuilding a castle wall that took very hard work to destroy. Jesus assumes that the Devil spends a lot of effort in possessing a soul. Sure if it was an 'easy thing' to re-posses another soul and just move evil around in a manner that would make it only seem a Messiah was casting it out, then possibly, but that is simply not the case. You can't move evil around at whim, sacking more castles at the flick of a switch. Besides Jesus in casting demons out also healed those whose minds and bodies had been ravaged by the possession. Therefore casting devils out can't be divorced from healing. Something which Satan has no power to do. Therefore we assume the Devil would not and could not oppose his own works as he would actually destroy his own efforts.
From a basic logical division of what kinds of people in this world that could perform miracles, I think we have a resolution of these two verses.
Performing real miracles / exorcisms
a. Miracles could be performed by believers through the power and will
of the Holy Spirit.
b. On rare occasions the Holy Spirit could use an unbeliever to perform
miracles also.
Performing fake miracles / exorcisms (lying wonders)
c. Believers could be deceived into thinking they have performed
miracles when they have not.
d. Unbelievers could be deceived into thinking they have performed
miracles when they have not.
e. Unbelievers could pretend to perform miracles when they know full
well that they have not.
Those claiming to have performed miracles are ‘unbelievers’ who truly think they have performed them, so we exclude a, c and e. Only on rare occasions can (b) occur because God has rarely made use of unbelievers in this way in the Bible (possibly Judas and Balaam are notable exceptions.) Therefore, the only possible large group that Jesus could be referring to who are damned and yet believe they have performed miracles are:
d. – Unbelievers could be deceived into thinking they have performed miracles when they have not.
In other words the key phrase is that 'they say' not 'they did'. They thought they were preaching something very close to the gospel and even doing things that seemed miraculous and yet never knew Christ. They were total shams without even knowing it.
Commentators differ in their views on this a bit but a good summary of the ideas supporting the line I am taking is here:
In their appeal these false prophets state that in the name of Jesus they had prophesied, driven out demons, and performed many mighty works. Jesus does not deny the claim that they had indeed represented themselves as his ambassadors and that in connection with the invocation of his name they had indeed performed astounding deeds. The question that divides commentators is, “Were these deeds genuine products of supernatural power or were they fraudulent?” 2 Thess. 2:9, 10 teaches that in connection with the coming of “the lawless one” there will be a mighty display of power, signs, and wonders, all of them false. Acts 19:13, 14 shows that when the seven sons of Sceva, a Jew, tried to imitate Paul’s exercise of miraculous power their attempt at exorcism failed miserably. There was also the similar failure of Egypt’s magicians to reproduce the third plague, which failure, as many see it, sheds doubt on the genuine character of their earlier “successes” (Exod. 7:22, 8:7, 18, 19). Does not all this point to the possibility that also the demon expulsions and other mighty works of which the false prophets of Matt. 7:22 boast had been nothing but sham? (Hendriksen, W., & Kistemaker, S. J. (1953-2001). Vol. 9: Exposition of the Gospel According to Matthew. New Testament Commentary)
The fact that these fake miracles are so deceptive that those who pretend to perform them actually convince themselves that they are real, means they may seem real to us as well. Therefore, we must have great suspicion of anyone who claims to perform them and at the same time does not hold to the gospel, or or who lives a sinful lifestyle. If they pretend to be like Jesus and say, 'Look believe me for my works testify that God has sent me', then we really have to test the miracles to see if they are sham. For example a healer comes to town and says many people were healed. Well have the submit the reports from their doctors months later to show they are still healed. Christ's miracles were iron clad and could not be denied. Then if they say, 'You are in danger of blaspheming against the Holy Spirit for distrusting my miracles', we know for sure they are liars, for the Bible calls us to test all things and then hold on to what is true. Not to be intimidated by empty threats. True miracles are never defensive against critical tests, they welcome them as a means to became more persuasive to those who might doubt.