Why is it on for example this page
http://www111.sakura.ne.jp/~arigase/doujin.htm (NOT WORK SAFE!)
written 舞Hi-○E instead of 舞Hi-ME or VA○KYRIE PROFILE instead of VALKYRIE PROFILE?? Is it to avoid problems with copyrights on the characters in those series or is it something else?

Another possibility is to avoid showing up on search engines.

Tho, I notice the ○s are printed on the mangas too.
Maybe for style, in addition to the copyright thing.

> Is it to avoid problems with copyrights
Trademarks, probably.

Same reason that people used to write UN*X for "Unix", to avoid (or to make fun of) trademarks.