So I'm using a PIC32, it's rated for 80 MHz operation. But my crystal might be inaccurate, so it could oscillate at 80.01 MHz. I can presume this is okay, but what if I were to use a 7.3728 MHz crystal and an 11x PLL, would running it at ~81 MHz be okay? I suppose what I'm asking is how far is too far? And why do manufacturers not include a bit of overun (for example rating it at 81 MHz?)
Well the right answer is "you can overclock until it stops working" .... more seriously something like bumping an 80MHz clock to 81MHz is not a big deal
(puts on chip designer hat) when we tape out a chip we don't have complete control over what happens at the fab - they might put a little too much dopant (or to little) in one step, or under etch a step so that wires are slightly wider (with higher capacitance) - instead we design for the 'worst case corners of the process' and try and make internal timing there - that way any functional chip coming out the other end should work and meet the spec - from you point of view it means that most of what you get from us is somewhere in the middle of the yield curve and happy to run over spec .... but some percentage will be just at spec and will fail if you overclock (and some percentage will go much faster still).
We don't normally test chips for speed (maybe sometimes a test patch on a dies to test the process) - it's way too expensive - we plan on them all working. Some expensive chips (high end processors for example) will get tested and binned because it makes sense for both practical (yield) and marketing reasons to do so
Manufacturers specify a maximum clock speed for a reason, as it guarantees correct operation under all conditions specified in the data sheet. Operating a device outside its specification might be OK in a hobbyist application, where an occasional failure can be tolerated, but isn't a good idea if reliability is important. You will have to test the system and see if it is sufficiently reliable for your requirements, under all circumstances.
I can't see 81 MHz causing a problem, but it can't be guaranteed.
In fact, most of these low-speed chips can work on 1.5x frequency in normal conditions, the only problems are at extreme temperatures (like -55 or 125) + flash/EEPROM writing.
So if you you are building device which will be operated at 15-40C range, you may test that it works at 120Mhz and leave at 100 permanently.
Manufacturers underspec devices to increase yeld rates & reduce reclaims.
If you're working with a single device you can just try and see what frequency still works. 81 MHz will still work, no doubt about it.
It's a bit different if you're working with production quantities. You can't make a production run and hope everything will be all right.
In the early 90's I worked for Philips Audio and we had a design which used a Motorola 56002 DSP running at 27 MHz. This was an audio application, and the 4th harmonic of 27 MHz is 108 MHz, just at the edge of the FM band. Because we feared interference we wanted to run the DSP at 27.1 MHz. Would this work? Yes. For sure? No. Motorola guaranteed it for 27 MHz, no more. We requested and got a custom version of the specification which stated 27.1 MHz as the maximum frequency.
Did we get different, selected devices, or was there a die redesign? Of course not, but in unlikely the event that a DSP would not work Motorola would be liable.
Back in the 1970's, it was pretty common to run 6502 microprocessors at above the rated speed, even though the data sheet gave a minimum cycle time of 1000ns for the 1MHz part. The popular Atari 2600 Video Computer System ran its processor at 1.1932MHz; the Apple II, Commodore VIC-20, and Commodore 64, all ran at 1.0227MHz. Since there were no speed grades between 1MHz and 2MHz, I would expect all of those machines were overclocked (by almost 20% in the case of the Atari 2600 Video Computer System).