Most encounters are scaled down by removing monsters from play. However, solo monsters are designed around a 5 player party.
What is the best way to scale them down to be an interesting fight for 2 people, preferably while keeping them a "solo"?
Solo's are supposed to be worth 5 normal monsters (thereby suitable to face 5 PC's ... erm ... solo)
Elite's are worth 2 normal monsters. I'd think you could re-template the solo as an elite and come pretty close to an appropriately tough encounter.
Use the XP Budget and don't alter the Solo- this is especially useful if the PCs are beyond a certain level.
What level is your party of 2? Let's say these are a pair of 7th level heroes. A 7th level monster is worth 300xp. Which means you can use around 600xp in an encounter for a standard, and maybe boost it up a bit for a harder one.
A level 2 solo is worth 625xp, and the one example from the compendium (a soldier-type) has an AC of 22 or so, and a main attack of +8. if that's not high enough you could get a level 3 solo: I think lurkers work well. If I made any alteration at all, it would be to change the attack bonus only to be the same as an equivalent level monster to the PCs. It's ok if the AC is low, and hit points are going to be arbitrary, regardless.