This guide to resolve any issues users get when they try to change nature or PID of a Pokemon from Gen 3 or Gen 4. DO NOT USE ANY POKEMON WITH MODIFIED PID ONLINE!
Foreword
The reason why people get various PID-Mismatch or Invalid Encounter type of messages, is because simply, they did not modify the Pokemon correctly.
In Generations 3 and 4, due to an in-depth understanding of how the Pseudo-Random Number Generator works (as well as game mechanics), the Personality Value (PID) is tied to various other values related to the Pokemon generation procedure in-game, such as Individual Values (IVs), Gender, Ability slot, Nature, and Encounter Slot. (Encounter slot refers to the programmed data in a table, that hosts a list of level and species that can be encountered in a map)
Resolution Process
For starters, I'll be using this shiny Deoxys, to attempt to change its nature to Sassy (while keeping it shiny).
Let's begin:
Download RNG Reporter
Change the stat you want (for example, nature) Pokemon in PKHeX, and set it into the box. Example, it looks like this now:
(other examples include Encounter Type Mismatch)
Identify which Method is appropriate. What is important is:
(More details at the bottom of the page under Note 1)
Find PID using RNG Reporter
Open RNG Reporter
Select the chosen Method
Indicate ID and SID and check Shiny Only, if the final result wanted is shiny.
Indicate Encounter Type (if necessary).
if you're going for a Pokémon that has an overworld sprite that isn't the Red Gyarados (Sudowoodo, Snorlax, Heatran, Giratina, Azelf, etc.) select Stationary Pokémon . The rest are self-explanatory. Most of the time you'll be picking Wild Pokemon as your method unless you're only going to capture legendaries, in which case you'd pick Stationary Pokémon.
Indicate the stat you want (IVs or Nature, or Gender for example)
Select starting frame at 1000
Click Generate. If you don't get any results, feel free to increase the Max Results. Example of results:
* If you are doing this for a Wild Pokemon, ensure that the result you've chosen, has the Encounter Slot that matches your species encounter slot on the route. To check the relevant encounter slots, refer to this website.
If RNG Reporter Main page doesn't give you any hits, consider using Time Finder. See Note 2.
In PKHeX, change the PID, Nature, Gender, Ability, and IVs to match what was generated.
Note 1: "Method" details
Method 1
Method H
Note 2