On the face of it, there's a distance between them that's akin to the gap between Sir Cliff and Marilyn Manson.
Here's Elvis, the onetime New Wave supergeek turned singer-songwriter's singer-songwriter, and Burt — the ageing king of American non-rock sophisto-pop.
But Costello has used many — too many — of his recent albums to show just how cultivated he can be.
Meantime composer-arranger Bacharach, who turned peddler of saccharin MOR in the 1980s, more recently became a name to drop as an influence among many artists for his classic 60s tunes. Yes, the passage of pop history has brought Burt and the Beatles together in one breath. And he was hip enough to get a cameo in Austin Powers.
It was another movie that first got the pair together, penning "God Give Me Strength" for the film Grace of My Heart, a story about a Carole King-like figure.
The movie was half-baked; the song, however, was glorious, even if it was ostensibly an exercise in recapturing a pop era and its period detail.
So too is Painted From Memory upon which "God Give Me Strength" is included as a dramatic finale.
Initially, it'd be easy just to smile at the album's respective trademarks — Bacharach's chilled syncopation and plush symphonic upholstery; Costello's tremulous balladeer's voice and wordplay. It comes on toe-tappingly tasteful.
Then, however, the songs really kick in. Soon the 12 tracks are treading the line between heart-warming and heart-wrenching with piano-led string-laden ballads, elegantly wistful pop, and jauntier jazzier numbers.
It's in the ballads like "I Still Have That Other Girl" or "What's her Name" (both which should find a place alongside Costello's "Alison") that Costello's performances really shine. Two words: channelling Frank.
It helps too that Costello has clipped his usual word count and upped the paint-a-picture to his lyrics. Though it's a picture of one unlucky guy.
Elsewhere the Bacharach factor shines brightly on "Toledo" with its muted horns and Latin bounce. Or when "This House Is Empty Now" comes out sounding like it could have once belonged to Dusty Springfield.
Elsewhere, the likes of the jazz-soul "Such Unlikely Lovers" or "The Long Division" suggest Steely Dan in their electric piano-framed frostiness.
And only the late arriving "Sweetest Punch" could have fitted on any other Costello album.
Here, despite the sophistication, Costello is more affecting than he's been in a very long time on an album of high dramatics, musical fireworks, sweet singing and bitter sentiments. Golly, it's lounge music's very own OK Computer. And it's sublime.