Are there locations/altitudes with minimum speed requirements? For example, a slower aircraft operating on the North Atlantic Track System would have an operational impact on surrounding/overtaking aircraft as well as potentially increasing ATC workload to ensure separation.

So, are there any formally encoded minimum aircraft speed/performance requirements based on operational environment?

(Maximum speeds are covered in this question and the topic of why aircraft aren't designed to operate at slower airspeeds is covered in this question.)
The way it works is you file your flight plan for the NAT with a proposed Mach #, but when you get your Oceanic Clearance they will assign Mach #s for each segment of the NAT and that's what you have to fly unless cleared for a different speed.  The adherence to assigned Mach #s are the only assurance of separation once out of radar coverage.

Perusing the NAT Operations Manual I couldn't find anything that gives a minimum Mach #, but if you were unable or didn't want to maintain the Mach # assigned, you would probably be given the option of flying down below RVSM airspace, or taking an off-NAT routing like the northerly "Blue Spruce" route (which airplanes use when they have to stop in Iceland for fuel because they don't have the range for the NATs).