In no particular order:
365N2 with the N3 tail rotor (you won't get a used N3, Ns are old and underpowered, N1s are worse).
S-76C or C+ maybe, though I'm no 76 expert. I gather the B is underpowered (or more correctly, too heavy... that's like the N1)
I like most of the Bells I've flown, but I wouldn't use 'em for SAR (they're crappy search platforms for one... they shake too much). I disagree with tail rotor comments about 365s... good crosswind authority once you get out of the N1 tail rotor, and the N3s t/r is the best so far. If you need more than 35kts crosswind capability, you might already be in some trouble. I've winched downwind, crosswind, in stack gas burble... I don't buy the tail rotor argument for a second. Also, if you're in that tight a space or have to land in the bush... it's hard to knock the blades off a 365 tail rotor. The 12,000' requirement might be pushing it for a N2, but I'm not sure of that... the N3 would do fine.
Most things smaller you're hard-pressed to put a large stretcher case in the cabin and work on the patient. I know, the clam-shell door machines are good for that, but they tend to be more of a specialty EMS machine, and those clam-shell doors do you no good in flight.
In short, everything's a tradeoff. Everybody likes what they know, but if your pilot's only flown a 412, how does he know it's best for the job? A 412 cruises at what... 110? A 365 or 76 will cruise at 140, so your Golden Hour radius just increased by 30 miles... look at a map and see if that matters to you or not.
Your pilot also might find he likes Sikorsky or stepping on the other pedal. A 412 is a pickup truck... a 76 or a 365 is more of a utility vehicle. Sort out the extreme cases on potential missions, get hold of some performance charts for the respective machines and play with those. Sounds like you don't want a mixed fleet, but you want something that can do everything you want adequately (normally the compromise one ends up with) and one or two things exceptionally. DOCs will also be a factor, and spares. There's no such thing as the perfect machine, but something in the 10000# region is probably where you want to be. I think if your pilot DOESN'T at least explore other alternatives when he has a chance to set something up from scratch, he's out of his mind.
Ay caramba! Where's my coffee?