FWIW, my (now ancient) Maine Coon was an excellent mouser in his day.
This would have ben effective for choosing the right one of our two cats. Also, our good huntress looks like she belongs in the WNBA, with a serious wingspan and upper (well, front) body strength.
A cat that’s was raised outside by its mom would probably be a good bet. That would ensure opportunities for hunting lessons.
I’m pretty sure my older cat has never even caught, let alone killed, anything bigger than a bug. So I wouldn’t agree that they are all effective as mousers.
I saw that too.
But our cat Bunn E. Kitt E. ( half Siamese/half American Shorthair. Pronounced BUNNY KITTY) was taken by his mother very young. He’s also never been nothing but strictle an indoor cat.
But when some mice got in the basement Bunn E went into full combat mode and got every one of them. So mousing might be a natural instict of cats.
I was talking about these.
I have a couple of Turkish Vans that are serious hunters. I don’t know if we would have ever had a mouse problem anyway, but we certainly don’t with them. Bugs survive about 5 minutes in this house. (They can leap straight up about 5 feet, and love catching moths in flight) The seek, attack, and destroy toys. Anything not solid material they will “skin”. They managed to disasemble any sort of automatic/mechanical or dangly toy we give them. Ours don’t go out, but our breeder has a big run in her yard-- their father once caught a squirrel. (They also play fetch like a dog, love water, and have coats like cashmere. They are interesting and unusual cats. Some of the lines (including ours) are only few generations from the wild, but they ADORE people.)
They are also, without fail, obsessed with laser pointers, and stalk and chase them with the same intensity. I second the suggestion of taking the laser pointer to the shelter.
The factory cats I’ve known were all “breed unknown” (some may have been classifiable but, hey, they were factory cats) and the only one who wasn’t a hunter didn’t hunt flapping coats, scarves or other dangling things, either.
One of the factories was choosen as a mating ground by a pair of urogallos (they’re big birds, somewhat similar to turkeys); watching the much-smaller cat watching the birds, getting close to the female when the male went far and freezing when the male got close, was quite a show. Slow production day too, pity we didn’t have popcorn 
The Maintenance guy shooed the birds away when he judged the female was at serious risk of not being able to lay eggs any more.
I’ve seen that sort of thing, but I’ve also seen the opposite - we had a young cat who would seem quite happy and content until some sparrows would land in our yard. The cat would then start whimpering and pacing up and down, showing neither aggression nor timidity. It seemed he was simply confused. I got the impression that the instinct to hunt was nearly gone, but still there in a vestigial way, and he was thinking, “I just know I’m supposed to do something with those bird things, but I can’t for the life of me remember what! I wish they’d just go away so I don’t have to think about it.”
The one thing about terriers versus cats - when a terrier brings you a mouse it’s a whole mouse, head and all. This is a plus.
Mama cat teaches her kittens the (crunching) killing bite.
I’ve never seen a Maine Coon that wasn’t a voracious predator. They’re tireless hunters. My parents had one that would kill five to ten animals a DAY in his prime. It was amazing.
We have one now and he’s an indoor cat, but his hunting insticts are as sharp as a razor. Everyone I’ve known who had one who let them outside reported an endless parade of victims left on doorsteps. They just love to hunt.
They’re also very friendly cats with people, so they’d be a good choice. They do eat a lot though, and in my experience will kill animals but eat your food.
Everyone I know who has a Calico cat seems to have a good hunter on their hands.
We have one, she’s probably about 10 years old now, indoor cat and has been (front) declawed, but can kill damn near anything her size.
We live in the city, but she’s still managed to take out 5+ rabbits, dozens upon dozens of mice, squirrels, chipmunks, lots of birds, basically, anything that’s killable.
And she’s not even that big, she’s on the small size for a house cat, but she’s the most effective hunter we’ve had, even better than the ex-barn coon cat (he only took out one mouse during his career).
A barn cat should be a good mouser. I’d ask your vet whether he knows of any barn cat litters. As stated above, the kittens learn to hunt from mama, so you should do okay with a 10-12 week old.
You never saw my aunt’s Maine Coon, Phil. The only thing he ever hunted was kibble. Very sweet cat, extremely mild-mannered (when I had to pill him he just got a confused look on his face and meowed a little bit). His reaction to stress (like getting examined at the vet) was to go to sleep. Big furry meatloaf of a lap cat.
He defended his yard against other cats but as far as I know he never bagged any prey.
That said, the Maine Coon was originally a “working cat” IIRC - barn/outdoors cat, mouser, etc. Maybe Phil was just bringing down the average.
You are probably reeling with all the suggestions, and I will add to the cacophony. I have had cats that were good mousers and ones that seemed more related to Garfield and would seemed to put forth the mantra, “Can’t we all just get along?”
The best I ever had was a semi-wild tabby who adopted me and kept a semi-rural house mouse free, while the neighbors were infested. Once she had kittens and they were farmed out to the neighbors there were no mice in the area. Clearly she taught her children well.
The only flaw was that she was very possessive of me and would virtually fight off any girlfriend I brought home. Once one girlfriend playfully slapped me and the cat bit her. When my wife and I paired up, the cat eventually accepted her, but kept trying to teach her how to catch rodents herself. She would bring still-living mice, rabbits, snakes, lizards, etc to my wife and drop them just as she would do with her kittens when training them and wait for my wife to chase and capture the offending small beastie. Instead, my wife would make shrill noises and run in place. The cat would just look at her totally perplexed. When the mice or whatever ran away, she would go get it again and drop it at her feet again.
She never understood what I saw in her.
Anyway, I am a big advocate of female cats being the best mousers, and I feel that going to a vet who deals with farmers would be a good source for good mousers.
Not really an answer to the OP, but one of the vets here told me that just the scent of cat, even if it was old, corpulant, non-hunting cat would keep the mice away.
I had a mouse issue at home that I posted about - I adopted my friend’s 18 year old avowed Non-Mousing cat and haven’t found any evidence of the mouse since.
Anyhow, perhaps that will make your cat selection easier. 
The cat or the wife?
Pretty normal cat behavior - as you said, kitty was trying to teach your better half how to hunt, like she would a kitten. I haven’t had to deal with this myself in a long time (and current cat is indoor-only model) but IIRC the proper way to handle it is to praise the little hunter profusely and then dispose of the dead/dying rodent when your cat isn’t looking.
I don’t know if the laser pointer test would help. My cat fears the laser pointer. We use it to curb her misbehavior (she is a dumpster diver), and she will run if you say I’ve got a LASER POINTER!"
But she is white-hot death to mice, wasps, spiders, centipedes and pony-tail holders. I don’t know if she uses a death bite, from the remains I would guess it was more like a salad shooter. She was a weaned barn-cat kitten.
Catophony?
An incorrect belief on their part.
Hunting mice is natural for cats, and they will do so even when well fed. In fact, overfed, overweight, very fat cats will still get excited about chasing a mouse. It’s just instinct.
Hungry cats will eat the mice they catch, often the entire body. Well fed cats will bring them to you for display, and might take a few bites from them, but often won’t really eat much of them. That probably reduces the slight risk that your cat might get sick from eating the mouse.