Recently re-installed TES III with a few mandatory mods (MGE, Code patch) and expansions, but I'm getting strange results with the ingame map:

http://i52.tinypic.com/hu4n48.jpg

I have no idea how to fix this or what could cause it... Help is appreciated.

This is usually caused by applying the Code Patch's "expand map" feature to an existing Save file (mid-game.)
You can try Wrye Mash's "Update Map" feature, but it usually doesn't correct this bug.

It should not appear in any New Games, but it will likely always be on this particular Save file.

I never touched the expand map feature, actually.

And Wrye Mash made it worse.

I have a similar problem, am using MCP and MGE, as well as Wrye's features, though your problem does look worse. The map on my game - no matter the file - goes crazy sometimes (too much to describe), and I did installed MCP before I started playing my current install. I would suggest, each time you play, start a new PC, just a dummy, get it to where you can use your menus, look at the map, and if it's not broken, load your desired character, and it might be fixed. If you don't use an alternate char generator, that's all very tedious, but it's solved some problems for me, or at least put a band-aid on it.

Is there any way to fix this issue? I used MCP's expand map feature too, but before starting a game. The character I created afterwards has always had this map issue, though any new characters I create don't share the problem.

I'd rather not have to start over from scratch just to get the map working again =(