This guide to resolve any issues users get when they try to change nature or PID of a Pokémon from Gen 3 or Gen 4. DO NOT USE ANY POKéMON WITH MODIFIED PID ONLINE!
Foreword
The reason why people get various PID-Mismatch or Invalid Encounter type of messages, is because they did not modify the Pokémon 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 Pokémon 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)
TL;DR: Due to how RNG is called, PID, IVs, Nature, Gender, Ability, Encounter slot are related and can be derived.
Basic Preparation
1. Pokefinder will be the tool we use to find correct information (PID/IVs etc)
2. Time and patience. I cannot stress this enough.
3. Know whether the specific Pokémon is Stationary/Gift or Grass/Cave/Surfing/Fishing/Rock Smash wild encounters.
4. Begin with 'priority of information' in mind. Which is more important: PID or IVs? That will be your starting point.
This will be basis for choosing Search via PID or Search via IVs below.
Note: Do know that there are scenarios where the PID or IVs you want would be impossible. Learn to adapt to such scenarios.
5. If you're trying to make a shiny, and TID/SID isn't all that important to you, ignore shininess for now.
(There's a Shinification portion further down. Run through the regular steps first)
Search via PID - Stationary/Gift
Search via PID - Wild Encounters
Search via IVs - Stationary/Gift
Search via IVs - Wild Encounters
Shinification