301 Redirects of old URL's

My site formally used a URL rewrite component called LinkFreeze to change the URL's to "SEO friendly URLs".
EX: 'www.mysite.com/category.asp?cat=3&subcat=2'  would be changed to  'www.mysite.com/category~3~subcat~2.asp'

Moving forward to 2018... I'm unable to use this component anymore so there are thousands of orphan URL's out there.  I wrote a simple script for a custom 404 page that redirects the URL to the correct (original) format of 'www.mysite.com/category.asp?cat=3&subcat=2'.  This works, but I was hoping there was a way to do a 301 redirect using URL Rewrite.  I'm open to any suggestions.
EddieWeb SlackerAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Shaun VermaakTechnical SpecialistCommented:
Did you try the URL Rewrite extension for IIS? What version of IIS are you using?

www.mysite.com/category~3~subcat~2.asp was never super SEO friendly links, perhaps opportunity to fix this?

SEO friendly IMHO looks like this
EddieWeb SlackerAuthor Commented:
Agreed, the link format was a bad idea from the start. Unfortunately, they are still out there for our site by the 1000's.  My 404 page redirects them to the correct URL format but I need to find a way to redirect them with a 301.  I'm using Windows Server 2012, IIS 8.   I'm confident the URL Rewrite will work but I'm not sure of the syntax.
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today

From novice to tech pro — start learning today.