My initial enthusiasm for 4E has cooled. I'm finding different problems than you state. I don't know that I feel like returning to 3.5, but 4E has some serious problems.
1. 4E is too easy past 1st level: I felt challenged at 1st level. But now that my group is 2nd and 3rd level, they are mowing through most encounters even with me boosting numbers to account for six people. The players have more powers than the monsters and usually better powers. They crush the monsters with ease making the entire encounter feel like not much of a challenge.
My group and I haven't found 4e to be easy at all- if anything, its far more deadly than any version of D&D up until now. Every battle, at least one character seems to go down, and in 6 levels, we've had 5 character deaths. Its brutal. If you're using standard monsters and minions, then no, they aren't as dangerous. Mix in an elite or solo, and characters will go down, and likely die.
While the PCs do have more powers as they get to higher level, so do the monsters. One of the most brutal encounters so far has been with a grell, two trog maulers, one trog impaler, and one trog curse chanter. At the end of the battle, 3 of the 6 characters were dead, and two more were down. That encounter was only one level higher than partly level, and both sides were rolling pretty average. Even encounters at party level or one level lower have KO'd or killed characters. Another one (when they were 4th level) involved 2 dark creepers, 3 zombie rotters, and a corruption corpse. The cleric kept botching his Turn Undead power, and the zombies were an effective screen for the creepers which kept getting combat advantage, while the corruption corpse hurled zombie poo continuously. A lot of the lethality depends on your tactics as the DM, and with 4e I feel more free to cut loose and throw everything I have at the party since they are a little more durable. However, some monster combinations are truly nasty, and lucky rolls for the monsters can kill PCs in a big hurry.
As for healing surges, my group runs through their full allotment in 2-3 encounters usually. We have a cleric, warlord, and paladin in the group, so we have a decent amount of healing, and the fighter has dwarven plate (which lets you use a healing surge as a free action). I also use a house rule that allows for long term injury if PCs go below 0 hp, so usually at least one character is somewhat injured at any point. That makes it somewhat more deadly than core 4e, but I'm also playing in a core 4e game, and the deadliness isn't much different.
I think most of the problem you're having might be you going easy on them or holding back on tactics, and the players really working together well and cooperating to have excellent tactics. I held back the first two levels as well, and noticed they had an easy time. Let them have it with both barrels, and it becomes a very different story.
2. The game is harder to run than 3.5: I kept hearing all this talk of 4E being so much easier to run and play than 3.5. That hasn't been my experience at all.
Like you said, the bookkeeping is found more in play now, but I have found 4e is MUCH easier to run than 3e. First, there aren't buffs to track- only some conditions. I use the Initiative Tracker with magnets for each PC and monster, and if a monster has a condition on it, I note it on the paper where the monster's stats are, AND put a magnet next to the monster's name on the tracker with the condition listed. If the monster gets bloodied, I use a red pen and write a big "B" next to its name. Basically, I have found using little tricks like magnets and markers to really speed up keeping track of things. And at 6th level, I'm having no problem- we can still get a round of combat done in 5 min, compared with 20-30 min in 3e.
And sometimes it doesn't help that minis are being used for battle. Minis have no numbers, so myself and the other DM sometimes make mistakes on who has been damaged and who hasn't in large combats because we don't recall what number a particular mini is.
Love to hear some suggestions from other DMs on how they keep track of damage to a particular creature when they are using a mini with no number designation in a large scale combat. I know I get lost sometimes. It hasn't had a huge effect on the game, but it is a bit frustrating to have to keep careful track of all the movement when the minis look the same for multiple creatures. When I used numbers on a grid map, keeping track was much, much easier.
Well, I find using D&D minis to be a bad idea, without some kind of marker on their bases to distinguish them, or without repainting them. I usually use painted pewter minis, so I don't run into this problem- I paint each mini differently and glue them in different poses so they are easy to keep track of, then I note which mini is which on the master combat sheet I make with their hp. Maybe if you paint the bases different colors, or use numbered stickers on the base or bottom it might help?
I also have players keep track of various conditions on monsters on a small erasable whiteboard, and when it gets to that critter's turn, I have them tell me that the effects continue or to make a save. I also have one player who writes down and records the init numbers for the party, then I add my magnets to the tracker with the monster's init numbers on them, then put the tracker out where everybody can see it. Have your players do a little of the tracking too- this was vital for running a 3e game, and it sure helps reduce my workload in 4e too.
For Keep on the Shadowfell, I am using the counters Fiery Dragon provided, free of charge. I printed them out on cardstock, using work's color laser printer, and cut them apart with my wife's scrapbooking paper cutter. I just write numbers in the circles provided.
