I am looking for some melodic black metal like catamenia's first three albums or windir.

A lot of people would consider catamenia melodic death metal but I do not want bands like children of bodom, insomnium, kalmah, etc. I like these bands but I am looking for something a bit closer to black metal

Try Cor Scorpii-Monument. It is the windir keyboardists band and almost sounds like it could be Windirs fifth album.

Graveworm and Mirzadeh

For Windir check out Mistur, Sigtyr, Feigd and some Vreid tracks you will prob also enjoy Galar. As for Catamenia try Cryptic Wintermoon, especially the first three albums excellent band. Aldaaron's new album is a more agressive affair but it is full of great melodies. Also try Forest of Fog and Norway's Sworn.

not sure if it's too similar but an often overlooked gem is Vargavinter's album "Frostfödd". classic, melodic BM from sweden in the mid 90s

Definitely Naglfar.

Thyrane might suit you with their first three releases and perhaps their very last one as well.
http://youtu.be/LvfR2uT_I4I Devil Messiah from Symphonies of Infernality
http://youtu.be/I_M-IGw_CMc Beneath the Banner of the Unholy Satan's Cult also from Symphonies of Infernality
http://youtu.be/WNANW-92PtI Chaotic Profane Phenomena from The Spirit Of Rebellion
http://youtu.be/9VZReUw-VhI Legacy of Saints in Disguise from Travesty of Heavenly Essence

Symphonies of Infernality (and their debut) are their blackest releases, Spirit of Rebellion shifted more towards a slightly more death and industrial style but maintaining still a few characteristics of black metal. Then they made a industrial "blackened" metal album not worth mentioning here and in their last relase Travesty of Heavenly Essence, they steered away from the industrial aspect again.

Achenar is very melodic black metal!

Check out here: http://soundcloud.com/achenarnorway/ach ... genstjerne