It must have been something serious, because if it were done for a petty offence it's not going to be credible -- and will cause alarm among other knights who feel their own titles might be in jeopardy. On the other hand, the offence can't be so bad that it's warranted harsher physical punishment (though he might have been fined or had lands confiscated).
A high profile example here is Lord Thomas Cochrane. His title "Lord" took priority over knighthood so he was called that (he was the eldest son of an earl) but he did have a knighthood (of Bath, earned in naval service). I see that someone else remembered him too while I was typing.
The accusation of fraud... Short overview of that..
In the first months of 1814, Britons were hoping to defeat France after 20 years of war - British and allied (Russian, Prussian, Austrian) armied were invading France after 20 years, but Napoleon was defending.
Lord Cochrane invested a lot of money gambling on victory: he bought a lot of government debt in form called "Omnium" which was quite volatile and was going to gain much value in case of victory. And gave his stockbroker standing instructions to sell his stocks if victory does come and the stock price rises.
On 21st of February, some pretended officers arrived with news of Napoleon´s defeat and death. The price of Omnium duly rose and Lord Cochrane (and some others) promptly sold their stocks.
Same evening, it was found to be fake news. Napoleon eventually was defeated (and surrendered alive) but it took another month and a half of war.
There certainly were some frauds involved. The people who brought the news were plainly liars. The question was who their accomplices were.
The man who arranged the fraud had met Lord Cochrane. Cochrane claimed he had talked of other business and had not let Cochrane in on the news being false.
In June 1814, Cochrane was tried... and after 12 days of trial found guilty by jury. The punishment: a fine, 12 months in prison, and to stand in pillory for an hour. The other defendants got similar punishments.
Public opinion was greatly divided - a lot of people thought him guilty, a lot - innocent.
His knighthood was taken away. So was his navy rank. The House of Commons voted to expel him... and the electorate of his constituency promptly voted to reelect him. The sentence of pillory was cancelled because of expectations of public reaction.
Now how did Cochrane get his knighthood back?
Not as long as the same king (Prince Regent future George IV) and same party (Tories) ruled.
However, when George IV died and was replaced by his brother William IV, and Tory party by Whigs, then the opinion changed... and early in 1832, Cochrane (by then he had inherited his father´s earldom of Dundonald) was given a pardon and got back his navy rank (and actually one rank promotion). But then not knighthood - on grounds that Cochrane had been duly convicted by a legitimate jury and court.
Cochrane, then 56 years old, refused to actually serve, on grounds that he had not got his knightgood back.
In the rest of William IV-s time and first years of Victoria, Cochrane was repeatedly given nominal small promotions of rank without actually serving. In 1847, when Victoria gave him back knighthood (and Cochrane was 71), he agreed to return to active service and actually did serve in active service.
When the degradation happened will also cause problems. If it was very recently, the person who degraded him is going to look foolish if s/he's now having to crawl back and reconfer the honour. That kind of thing makes a ruler look weak, which then undermines his/her authority; it also causes resentment amongst other knights/courtiers if they don't like your character.
That actually seems far less believable to me than having the knighthood re-conferred. Knighthoods are given for a lot of reasons, but that seems a dubious one, even if magical powers aren't widespread. Far better that he was originally knighted for something he did.
In a world where magic is real but rare and valuable, I don´t see it as awfully improbable.
And for me this is wholly unbelievable. Outlaws are renegades, and punishment for them is harsh. Forget tales of Robin Hood. Frankly, if you're stepping so far outside genuine historical mores in this way then I can't see why you're worried about reality as to why and how a former knight would be knighted again.
Reversals of outlawry were common. Robin Hood was problematic precisely because he was a yeoman. But noble outlaws? Henry VII was an outlaw, and his first Parliament was faced with the legal puzzle as to whether his own outlawry needed formal lifting or ended automatically by his victory at Bosworth. A number of revolts/civil wars were resolved by compromise... which included pardoning outlawries.
Now a question is whether a knight in open revolt, or a fugitive after a failed revolt, is a knight during the revolt. And this is something on which the king and the rebel´s comrades may well disagree!
That might allow the monarch/whoever to ignore his outlawry, but why re-confer the knighthood? What good does it do? If your character has demanded it as a price for his co-operation (though keeping his head attached to his body is all he might expect if he's been captured), then you need a good reason for it since it doesn't of itself provide him with money or lands, not does it automatically confer the respect of his peers or those under him.
Thomas Cochrane got job offer with his pardon and restoration of rank in 1832. He had his father´s lands unmolested (apart from the £1000 fine that he had paid). Yet he refused active service (and active service pay) till he got his knighthood back in 1847.
As for the issue of his being an assassin, while Brian is right as to the historical nature of them, I don't think it's an issue -- you're just using a common accepted term for a hired killer, and I'm certain there were plenty of those around in medieval Europe in one guise or another.
There are two issues here IMO:
1. Knighthood - there's no central authority for this, it's effectively just any lord who wants to reward one of his men with authority and title. So if any lord wants to give a person a knighthood, that's their business, regardless of their past. And in the European mediaeval period, many people had murky pasts.
That varies wildly depending on period and region. As late as 14th century, it was not just lords who could confer knighthood. One Robert Knolles, Esq., then about 34 year old, was accepted as commander of an army of 2000...3000 men, including several knights. After successfully besieging the city of Auxerre, his two subordinates who were knights conferred knighthood on him - and it was generally accepted elsewhere as valid.
By 16th century, however, English knights and lords no longer were allowed to confer knighthood. Commanders of expeditionary forces were allowed to do so, but the permission to confer knighthood was expressly named in the letters of appointment by English monarch. In 17th century there were some experiments allowing colonial governors to create knights; but it seems that after 1700 no commanders of British expeditionary forces had that right nor any colonial governor except that of Ireland (and in 18th century, Lords Justices of Ireland).
Cochrane served in three navies while a convicted crook. Chilean, Brazilian and Greek. Since particularly Chile and Greece were republican rebels against established monarchy, Cochrane was arguably an outlaw. For the same reasons, Chile and Greece were not into making knights or lords. Empire of Brazil did make Cochrane a Marquess of Maranhao, though as a lifetime title. Did Cochrane, or his contemporaries in Britain, act as if "Marquess of Maranhao" outranked his lower British titles "Lord Cochrane" and "Earl Dundonald"?
