As far as I know they can be used together.
I would be more careful combining it with other mods because I think the Patch Project mainly alters content. (?)
I suspect that you probably shouldn't use it with Morrowind Rebirth because it might result in inconsistencies in the game. - I just checked and it seems they include the changes in Morrowind Rebirth.

I haven't got much experience with the Patch Project, which is something I should change because I'm sure that the Patch Project is great.
If in doubt, I would use the Code Patch only, though.

I intend to keep mod use to a minimum using only a few like Fair Mana Regen, delayed Dark Brotherhood attacks and the Bloodmoon latest rumors fix, I won't be using any graphics mods (aside from a widescreen fix) or drastic complete changes. Mainly, I just want to make sure serious quest-stopping bugs are fixed.

Sounds unproblematic to me. Wasn't Fair Magicka Regen (If that's the mod you mean) bugged, though?

I highly recommend trying mods like Tamriel Rebuilt, Morrowind Rebirth, mountainous red montain. Abot's mods and graphics mods like Vurt's tree replacers -to name a few- sometime.
Believe it or not, there are mods that blend in completely but make the experience so much better.

I haven't played Arktwend and Myar Aranath for a couple of years, so I'll copy the overview from the homepage of these mods:

Arktwend
- Link: http://sureai.net/games/arktwend/
- Overview: "For an orphan, raised in the cloister of the small island-state Melee, it is now time to go its own way. But already after the one first night in freedom, everything takes its disastrous run."

Myar Aranath
- Link: http://sureai.net/games/myararanath/
- Overview: "Armies of Ahroma attacked Myar and exploited the country. But after the victory in the first war, parts of the country were freed and affiliated to the newly established realm of Fallas. But many regions are still left in the hands of the enemy. Recently rumors were coming up, saying that the Black Citadel of Narathzul was rebuilt, even bigger and more powerful than ever before."

Swords of The Perithia (SOP)
I just discovered the link below, but haven't used it myself.
Link: http://www.gamepressure.com/download.asp?ID=2756
Description: "SOP offers a new Main Quest and storyline. The entire game is set in a new Kingdom. 5 new cities (Balmora sized and bigger), with several new towns and camps. Over 100 new NPC's to interact with. Countless dungeons and interiors to explore. Over 80+ hours reported game time. New monsters with new skins. New weapons and armor. A whole new look and feel. Over 100 new side and misc. quests, not to mention a huge main quest. A much more puzzle based game, similar to the old "Link to the Past, The Legend of Zelda". New classes, and spells. A Haunted Forest, Massive Desert, Tall Mountain Peaks, Huge Waterfalls, Raging Rivers, Magical Forests, Pirates, and Giants, and Much much more! "

Personal Comment: SOP is complex, huge and quite tough. You start at level 1, but the fights are a lot harder than those of the original Morrowind (you may consider lowering the difficulty temporarily - better than desperating and losing interest). Definitely not recommended for a Morrowind newcomer.

Make sure you read the readme files before installing the TC's. If you are advised to backup certain folders or files before installing, you better do so. For example, you should backup the Morrowind.ini before installing SOP (otherwise you may encounter weird weather effects when you return to the original Morrowind).
If you have disk space enough, create a new copy of Morrowind, and install the TC to this copy.

Morrowind is my favorite game of all time, bar none. Here's my list of must-have mods:

* Morrowind Graphics and Sound Overhaul: Already posted above, but if you get just one mod, get this.
* Less Generic NPCs: Make almost all NPCs in the game have more interested things to say, back-stories, etc.
* Abot Water Life: I consider Morrowind incomplete without it. Adds loads of fish and other aquatic creatures to the game. Includes a fishing pole and the farther away from shore you go, the bigger the fish get (sharks and even whales).
* Abot Silt Striders: Amazing mod that makes the Silt Striders actually carry you in real time to your destination.
* Abot Boats: Same as above, but for boats.
* Animal Realism: Makes Slaughterfish, Rats and Cliff Racers less aggressive. Makes the game way less annoying.

There are other mods I use, but I can't play the game without the above. They are all fantastic and greatly improve the game's atmosphere.

Edit: Oh and a shout out for Tamriel Rebuilt, a mod that basically doubles the size of the game world. In the thousands of hours I've spent playing Morrowind I've never actually had the time to go there, but I've heard the content is very well done.

Fair Magicka Regen is bugged? How badly?

I've also used the EXE Optimizer, the 4GB patch and the Morrowind FPS Optimizer (for widescreen). I also plan on using Script Tidy. Does the order in which I install these patches and mods matter?

I've just checked and couldn't find any hint about bugs anymore. It might have been an earlier version that was bugged.

I haven't got any experience with GOTY Script Tidy.
I wonder if there is any documentation about how all patches work together.

[url=http://www.uesp.net/wiki/Tes3Mod:Exe_Patches]http://www.uesp.net/wiki/Tes3Mod:Exe_Patches[/url]
" Morrowind Code Patch FAQ
Provides the ability to fix many bugs which cannot otherwise be fixed (most notably the savegame corruption fix).
Also offers many tweaks and gameplay changes (such as expanding the playable map area).
All bugfixes and other changes are optional.
Must be applied before other exe patches.
Exe Optimizer
Improves the stability of the executable, thus reducing CTD's.
4GB Patch
Expands the virtual memory acces of the (32-bit) executable file from 2GB up to 4GB.
Should be the last exe patch applied."
A bit strange that the 4GB patch should be the last patch applied... does that mean you should repatch Morrowind everytime you changed Code Patch settings?

Yes. 4GB Patch has to be applied as the last one. Otherwise, MCP might not recognize the already altered .exe file. So if you did MCP > EXE Opt > 4GB Patch, which is the correct order, you need to apply EXE Opt and 4GB Patch again after changing anything in MCP.

I'm wondering if MSGO is going to actually get updated again because it's a bit outdated now, as it uses an old version of the Patch Project as well as not having other fixes (https://www.reddit.com/r/Morrowind/comments/19ycge/morrowind_modding_guide/).

Has the author MSGO finished with it entirely, or will it get updated with all that stuff eventually?

I really don't have the patience for MW modding anymore, just one installer than does everyone is fine for me.

I saw this recommended as the best mod in terms of patching up the sounds and graphics
http://www.nexusmods.com/morrowind/mods/36945/?

My big beef with Tamriel Rebuilt is that it conflicts with Beyond Ysgramor.

Am I missing something? I don't understand your explanation.
If MCP might not recognize the already altered .exe file then you wouldn't be able to "change anything in MCP".

Or do you mean that you should backup your Vanilla Morrowind.exe so that you can apply MCP again and then apply the other patches?

I appreciate that you told me you really have to apply the 4GB patch after MCP, though. Where did you get that info from? From uesp.net?
And why don't you experience these mods with different characters?
Even if you only occasionally use the mod being able to visit the main land offers a huge amount of role-playing possibilities.

Maybe it would be even a good idea to merge the mods - the amount of work needed to do that might be smaller than creating a new faction for Tamriel Rebuilt etc.

You can manually backup Morrowind.exe, but MCP doest that for you, too, it saves backup as Morrowind.Original.exe. When you click "Uninstall All Patches" in MCP, it just brings up the backup, it does not "reverse" the previously applied patches. So using the Uninstall button in MCP should be as sufficient as manually doing backups.

I got that info at Bethesda's official forums, there are a ton of informations about modding and technical stuff. Lots of talk about mods. The official forums are also home to threads specifically about such tools like MCP, where their authors post every now and then.

As far as I know, MCP checks the .exe checksum before applying any patches. Mere change in anything, and the checksum changes, and MCP may not recognize it. Because of that, different releases or language versions, usually having some differencies in .exe files, had to be checked by MCP author so the program can properly patch them.
I did some testing & stuff for Polish version of it, and I tell you, the MCP author does magic - when he told me to edit some bits of the .exe in HEX editor, it was all gibberish for me! Fortunately his instructions were clear enough.

Thanks for the names, but I need links and a brief description to add them to the OP. I simply don't have time to go searching for all recommended mods.

I have no personal time to really tweak mods, but it has been almost 7 or 8 years since I last tried and gave up on Tamriel Rebuilt, so maybe it is better.