Sorry, should have included that, Disco - Rodríguez Peña 1430 between Las Heras and Juncal in Recoleta. Believe it or not but they also had Horse Radish, first time I ever saw that in Buenos Aires in 23 years of living here. But Disco is horrible with their stock, things come and go, I'm pretty sure they still have relish but not the horse radish.
Also, in the same block is a really good Asian market called Matcha Life - Rodríguez Peña 1336, almost at the corner of Juncal by the fountain, they have a lot of hard to find things, like spices, garlic salt, frozen pot stickers, even really good frozen pork buns, that I used to have to go to Barrio China to get.
Good luck!