I'd suggest:

function removeKeyStartsWith(obj, letter) {
    for (var prop in obj) {
        if (obj.hasOwnProperty(prop) && prop[0] == letter){
            delete obj[prop];
        }
    }
}

JS Fiddle demo.

Incidentally, it's usually easier (and seems to be considered 'better practice') to use an Object-literal, rather than a constructor, so the following is worth showing (even if, for some reason, you prefer the new Object() syntax:

var map = {
    'XKey1' : "Value1",
    'XKey2' : "Value2",
    'YKey3' : "Value3",
    'YKey4' : "Value4",
};

JS Fiddle demo.

If you really want to use regular expressions (but why?), then the following works:

function removeKeyStartsWith(obj, letter, caseSensitive) {
    // case-sensitive matching: 'X' will not be equivalent to 'x',
    // case-insensitive matching: 'X' will be considered equivalent to 'x'
    var sensitive = caseSensitive === false ? 'i' : '',
        // creating a new Regular Expression object,
        // ^ indicates that the string must *start with* the following character:
        reg = new RegExp('^' + letter, sensitive);
    for (var prop in obj) {
        if (obj.hasOwnProperty(prop) && reg.test(prop)) {
            delete obj[prop];
        }
    }
}

var map = new Object();
map['XKey1'] = "Value1";
map['XKey2'] = "Value2";
map['YKey3'] = "Value3";
map['YKey4'] = "Value4";
console.log(map);
removeKeyStartsWith(map, 'x', true);
console.log(map);

JS Fiddle demo.

Finally (at least for now) an approach that extends the Object prototype to allow for the user to search for a property that starts with a given string, ends with a given string or (by using both startsWith and endsWith) is a given string (with, or without, case-sensitivity:

Object.prototype.removeIf = function (needle, opts) {
    var self = this,
        settings = {
            'beginsWith' : true,
            'endsWith' : false,
            'sensitive' : true
        };
    opts = opts || {};
    for (var p in settings) {
        if (settings.hasOwnProperty(p)) {
            settings[p] = typeof opts[p] == 'undefined' ? settings[p] : opts[p];
        }
    }
    var modifiers = settings.sensitive === true ? '' : 'i',
        regString = (settings.beginsWith === true ? '^' : '') + needle + (settings.endsWith === true ? '$' : ''),
        reg = new RegExp(regString, modifiers);
    for (var prop in self) {
        if (self.hasOwnProperty(prop) && reg.test(prop)){
            delete self[prop];
        }
    }
    return self;
};

var map = {
    'XKey1' : "Value1",
    'XKey2' : "Value2",
    'YKey3' : "Value3",
    'YKey4' : "Value4",
};

console.log(map);
map.removeIf('xkey2', {
    'beginsWith' : true,
    'endsWith' : true,
    'sensitive' : false
});
console.log(map);

JS Fiddle demo.

References:

• Object.hasOwnProperty().
• JavaScript Regular Expressions.

You can get it in this way easily.

var map = new Object(); 
map['Key1'] = "Value1";
map['Key2'] = "Value2";
map['Key3'] = "Value3";
map['Key4'] = "Value4";
console.log(map);
delete map["Key1"];
console.log(map);

This is easy way to remove it.

Preconditions

Assuming your original input:

var map = new Object();

map[XKey1] = "Value1";
map[XKey2] = "Value2";
map[YKey3] = "Value3";
map[YKey4] = "Value4";

And Assuming a variable pattern that would contain what you want to keys to be filtered against (e.g. "X", "Y", "prefixSomething", ...).

Solution 1 - Using jQuery to Filter and Create a New Object

var clone = {};

$.each(map, function (k, v) {
  if (k.indexOf(pattern) == 0) { // k not starting with pattern
    clone[k] = v;
  }
});

Solution 2 - Using Pure ECMAScript and Creating a New Object

var clone = {};

for (var k in map) {
  if (map.hasOwnProperty(k) && (k.indexOf(pattern) == 0)) {
    clone[k] = map[k];
  }
}

Solution 3 - Using Pure ECMAScript and Using the Source Object

for (var k in map) {
  if (map.hasOwnProperty(k) && (k.indexOf(pattern) == 0)) {
    delete map[k];
  }
}

Or, in modern browsers:

Object.keys(map).forEach(function (k) {
  if (k.indexOf(pattern) == 0) {
    delete map[k];
  }
});

Update - Using Regular Expressions for the Pattern Match

Instead of using the following to match if the key k starts with a letter with:

k[0] == letter // to match or letter

or to match if the key k starts with a string with:

k.indexOf(pattern) // to match a string

you can use instead this regular expression:

new Regexp('^' + pattern).test(k)
// or if the pattern isn't variable, for instance you want
// to match 'X', directly use:
//   /^X/.test(k)