It took me 7 years to get to the point in 3.x (well 3.5 really) where I could have a successful BBEG encounter.
The party was 13th level, the BBEG was a CR 17 Ulitharid with a few levels of psion to boost up his powers and he had six level 5 minions (level 5 Bo9S NPCs). The battle was the most climactic battle I'd ever run. In the beginning, the cleric/paladin went up against the Ulitharid, while the Ninja, Wizard, and Favored Soul stayed in back taking care of the minions. Until the cleric/paladin got grappled, in which the wizard used a spell that let him transpose positions with an ally, and having freedom of movement on so he couldn't be grappled.
The BBEG was tough, in the last few rounds, it came down to the BBEG dropping 2 of the 4 characters into negatives, when the cleric/paladin scored a hit with his abberation-bane weapon killing the BBEG the turn right before he would have been dropped. Very close, very climactic, and very fulfilling to have the battle go pretty much exactly how I wanted it to.
I certainly hope that it's easier to create solo encounters like that in 4e without being 4 levels ahead and minions to wade through.