It's probably not the localization that takes so long. I have a friend who works for Natsume of America (Harvest Moon series, etc.), and the approval process is what they have to deal with. Sony worries about limited store shelf space, and weighs the possibility of something that might sell (to people besides us) taking away shelf space from a game (such as Final Fantasy, SC2 or whatever) that they feel is sure to make them money.
And before more Sony bashing starts, this is true of all companies (so bash everyone). Natsume has a Wizardry game for GBA (that I did the American box art for) that has been localized and was scheduled to be released last year. Then it got pushed back to Q1 2003, and now it's on indefinite hold, because the GBA software market is especially saturated.
When I heard Metal Slug's American release was rumored to be cancelled, I was extremely disappointed, but not surprised. I very much hope it will be released here, but I think it's too early to tell whether it will make it or not.