Master of Orion 2 is still one of my favorite games and I come back to it from time to time. Expecially after seeing some kind of SF movie. After all it can't be so hard for the Federal Planets to beat the Klingons. Or I want to play the evil Cylons and blow up some planets.
However it is not easy to beat the computer on the impossible level. You need to use every trick in the book and change your strategy depending on your galaxy settings. What I am describing here is the strategy to beat the odds in a pre-warp, huge galaxy.

If you choose different settings (e.g. small or technological advanced galaxy) you will need a different plan. By searching a little you might find strategies to win small advanced games in a couple of turns. In my personal opinion pre-warp is harder than any of the other options as it will allow the computer to use it's cheating to the fullest. And don't be naive. The computer players are cheating. When you only managed to build your first colony ship the computer often already has three colonies. Or he will appear with a fleet of eight battleships when the upkeep of even two is almost impossible for you.

Computer players

The computer players will seem to research much faster as a human player. When the history graph shows that you are researching five times as much as everybody else you still will find that suddenly they have plasma cannons and phasor rifles. Also they tend to be very generous in sharing their archievements with their fellow computer players (or being spied upon). In a bad case you will look into the business ends of stellar converters from all enemies after leaving just one computer too much freedom.
If you manage to get galactic lore early in the game you will see that the computer has full knowledge about the galaxy. The computer players will never loose a scout to a space monster. They won't even use scouts but directly pick the best planets right away.
The computer players are also using their seven to one benefits. They will research only one topic while getting the other technologies through spying. Also usually one of the computer players will have a much better starting position than you.
In summary you will need to play better than the best of the computer players to win.

Custom race

There are a lot web-pages out there describing the benefits and drawbacks of all the options you can take. Reliable winning (>50%) can only be done by a custom race. I have two preferred races. One a creative unification race with large, rich, artifact planet. Another is creative democratic aquatic.
Unification will give you a substancial bonus for production which you will need in the colonization phase. It also gives you a small push from the beginning as you don't need so many farmers.
Creative is very usefull. Your ships will be much better than the enemies e.g. by always having the best computers. Also you will have a lot of junk tech to give to other races which usually means that you can befriend them long enough to get a head start.
A lot of games without creative were very frustrating. My ships constantly failed to hit with beam weapons, had just not enough range to reach interesting planets and I had to waste a lot of research points to get tech that I really needed right now (e.g. radiation shields or scanner technology). Also I really had problems making alien races happy. So save yourself some grief and be Creative.
Aquatic can be very helpfull. It essencially upgrades oceanic and terran planets go gaia. That means that most of the better planets will not need to be terraformed at all. Also it gives you a benefit in population size and food production right away since your starting planet will be oceanic (and thus considered gaia).

Basic skills

To survive on the impossible level you will need to master a couple of skills. Some of them could be considered micromanagement but they will improve your game by the amount needed to win.

Production stockpiling.

Every production (that is not considered pollution) goes into a production stockpile. It might look like the workers are building something but that's not really so. Actually there is no loss changing the goal half way through. So it might make sense working for the most costly battleship until you actually need the production (maybe for an emergency missile base). In the meantime nothing is wasted.

Housing colonies

These are colonies that are just used to produce new inhabitants for the "real" planets. After you experienced how a large ultra-rich planet builds a doomstar (during ten rounds) you will not expend money, production and thoughts on smaller planets. Except for two things: Autolabs and population. Planets with one inhabitant build grow as fast and sometimes even faster than bigger planets. So here is what you do: Build a colony base to settle anything better than "poor" planets in the same system. On this base build an automatic factory and a cloning center and then set the colony for housing. As soon as the population grows ship the new citizen to your main planets to grow them fast.
If you are good a this you will build up a new planet within very short time.

No taxes

Taxes do not reduce the morale on planets as you might expect after playing Civilization. They reduce the production on all planets with is something that you definitely don't want. So keep taxes at zero and instead place dedicated planets on "trade-goods" if you are running out of money.
If you go to full war you might very fast run out of command points and start paying big time for spaceships. I recommend that you just do more trade goods and continue. After all you are building those battleships for a reason.

Overkill while attacking Orion. In this game I waited until around turn 300 to attack the guardian with a death star and attached titans.

Killing space monsters.

Killing space monsters is quite easy and gives extremly good planets. Actually the planets you get from a space monster are usually as good as three "normal" planets and you still only need one colony ship to settle them. The tactic against space monsters is to have many small ships sending missiles and interceptors on their way and then running in all directions while the missiles hit one by one. Five frigates should be enough most of the time. Some small ships (frigates or destroyers) will be killed by one monster attack so giving them any protection at all is usually just a waste of missile space. Also monsters don't have ECM so ECCM missiles are not needed. Production needed for such a monster killing fleet is minimal but I recommend saving the game before launching the fleet. Quite often you are just one frigate short and might lose the complete armada.
Space eels need a little different tactic but are the easiest of them all. You will need a ship with some armour and then give a point blank head shot to prevent the missiles destroyed by the eels field.
The good thing about a monster killing fleet is that after the first monster it should be almost ready for the next one so no production is wasted.

Naming ships

Maybe not a vital skill, but something to be creative. I try to come up with a new scheme every time. For the beginning start with hand to hand weapons. That will give a kind of WingCommander feeling.
Dagger, Rapier, Broadsword, Morningstar,..
Snakes are also good. there are a couple of nice names like:
Sidewinder, Rattlesnake, Boa, Coral Snake, Adder, ...
Also gods make up good names. Master of Orion already proposes Nemesis. Other ones could be:
Pan, Zeus, Io, Jupiter, Mars, Hera
Lately I used star signs or chemical elements. With the elements you have enough to choose and they even have real cool names as Beryllium or Mercury.

Game walk-throughs

Now that we have covered the basics you can go to the game walk-throughs. I needed to split them up in two separate pages since depending on your race they are very different. With a production oriented race you need to aggressively use your benefit and start producing right away. With a science oriented race you don't want to waste man power on producing stuff when you can get a lot more benefits from having them research robotic factories or other production increasing technologies.
Click here for the creative unification walk-through
Click here for the creative democratic aquatic walk-through