Malladin's Gate is a carefully constructed name. We did have the name Black Orifice Games (although Nigel prefered 'Productions') when we were intending to publish our own non-D20 game, intended for a mature audience. When we decided to jump on the D20 fantasy band wagon instead we needed something a bit more family-friendly.
The issue was discussed over a phone call where we decided we needed something fantasy-oriented.
I had just been playing Baldur's gate, and so siad "we need something like baldur's gate".
Nigel said, "What about someone else's gate"
At the time we were developing our own fantasy setting for release by this about-to-be-named company (which we now have released in the form of the DarkLore campaign primer). Anyone who is familiar with this setting (which is probably not many of you, given the proliferation of PDF settings, even one as relatively successful as DarkLore) will be aware that Malladin is a significant historical figure from that game world (a wizardly Charlemagne). Hence we used the name Malladin and came up with Malladin's Gate. A few other options were considered before 'press' was settled on finally, but it was my first suggestion, if memory serves.
That's probably the longest explanation as to where the name came from, but there you go.
cheerio,
Ben