I have found a way to make pushpins appear above polylines, but currently only in Firefox (and other browsers that use SVG). I'm confident that something very similar will work for IE but I've decided to stick with Google Maps, so hopefully someone will complete the solution and post the rest.

The driving directions polyline on local.live.com appears in a different place in the DOM tree to polylines added using the API. By moving the added polyline to this location, it can be made to appear underneath pushpins. This is true of both SVG and VML, but the VML polyline seems to be recreated in the wrong location every time the map is panned.

An extra function is also needed to make sure the SVG div stays in the correct place, otherwise it will move 2px for every 1px the map is panned.

Here's a demo:http://www.goflying.org/maps/ve_track_display_demo.html

And this is the relevant code:

var map = new VEMap('map');
map.LoadMap();
map.AttachEvent("onendcontinuouspan", fixSvgDivLocation);
map.AttachEvent("onclick", fixSvgDivLocation);
map.AttachEvent("onendzoom", updateSvgDivLocation);

// Add polyline and pushpins

var innerMapDivs = document.getElementById("map").firstChild.getElementsByTagName("div");
var innerMapSvgDiv = null;
var divNum;
for (divNum = 0; divNum < innerMapDivs.length; divNum++) {
if (innerMapDivs[divNum].getAttribute("id") == "svgCanvas") {
innerMapSvgDiv = innerMapDivs[divNum];
}
}

var outerMapDivs = document.getElementById("map").getElementsByTagName("div");
var outerMapSvgDiv = null;
var divNum;
for (divNum = 0; divNum < outerMapDivs.length; divNum++) {
if (outerMapDivs[divNum].getAttribute("id") == "svgCanvas") {
outerMapSvgDiv = outerMapDivs[divNum];
}
}

var svgDiv = outerMapSvgDiv;
var svgDivTop = parseFloat(svgDiv.style.top);
var svgDivLeft = parseFloat(svgDiv.style.left);

document.getElementById("map").firstChild.replaceChild(outerMapSvgDiv, innerMapSvgDiv);

function fixSvgDivLocation() {
if (svgDiv) {
svgDiv.style.top = svgDivTop + "px";
svgDiv.style.left = svgDivLeft + "px";
}
}

function updateSvgDivLocation() {
if (svgDiv) {
svgDivTop = parseFloat(svgDiv.style.top);
svgDivLeft = parseFloat(svgDiv.style.left);
}
}

Hope that helps.