So, You Want to Challenge 3.5e Players?
Firstly, let me remark that KRyan's response is superb and has my vote. I wanted to take a step back, though, and respond to the question: "How do I challenge my party?" without reference to the specific scenario.
I'll outline a few things I do in my campaign that heightens the challenge without necessarily turning every encounter to a TPK time bomb.
Creative Things
Variety is the Spice of Life. I try very hard to make each encounter unique in some way. One session we'll be crawling a subterranean dungeon. Another time we'll be on an open mountainside where upper ground is an important thing. Another time we'll be on airships, separated by 500 ft' of sky. Yet another time we are stealthily infiltrating a Great House. Each session highlights the benefits of different skills. This way, we avoid one character always feeling excessively challenged while the others thrive.
Play like a PC. If your players are going to optimize their characters for this or that, it should come as no wonder that they trample over encounters of their level. I can relate with you on the struggle of building leveled NPCs, on the grounds that they take a lot of time to create, and they're thrown away almost as soon as the ink dries on the character sheet. Even so, if you want to challenge players, you have to play like a player yourself. The DMs cast of characters and monsters should behave as intelligently as you can excuse, given their Int score. Sometimes the difference between offering a challenge and offering cannon fodder is a little preparation.
Implement Custom Challenges. We had an airship battle where the PCs hardly took any damage at all... but the ship sure did. We were using Stormwrack rules, adjusted slightly to reflect airships instead of naval ships, and the party knew that if the ship sustained enough damage we were all going to die. Personal AC, DR, and saves were not nearly as important as creatively disabling the enemy crew from more than 400 ft. away.
You can implement all sorts of custom challenges to shake up player preconceptions and urge them to think creatively. In one encounter, you can deny the mage a spell components pouch. Now she has to figure out how to solve things using only verbal or somatic spells. Have the party defend a caravan, requiring them to think outside of themselves. These are all just ideas, but the point is that custom challenges shake things up and get players out of the break-down-the-next-door-and-kill-everything-that-moves mentality.
Adjust the Difficulty Both Ways. Unless your group really enjoys living on the brink of death, don't take them there every encounter. A trap with a modest DC, a weak sentry, a comfortable social encounter, and so on can bring needed tension relief to the group. When you grant your players situations that they totally own, it makes the subsequent encounter that is two or three EL above the party exceptionally tense and rewarding.
Try out 3rd-Party Modules. I take great pride in the fact that I write our adventures. It is a great deal of fun as a DM. But I'd be lying if I didn't say that the most fun we ever had was playing through the Banewarrens, a 3.0e module by Monte Cook. This module completely opened my mind to new ideas in encounter and adventure design. And even better? I still get to write our content; I just inject generous amounts of the 3rd-party content right along with it. If you're willing to spend $10-$20 on some commercial modules, you'll get loads of ideas and deliver some interesting challenges to your PCs at the same time.
Things to Avoid
Getting Personal. Unless your players really enjoy having personal challenges, avoid designing encounters that exclusively target a character's weakness. Consistently pitting the party against mages interested only in mind-controlling the barbarian (which is pretty easy to do) will make the player regret his character choice, rather than offer a real challenge. Focus instead on creating diversity in your encounters so that all players must occasionally adapt their playstyle.
Killing. Well, let me say that the second funnest experience I ever had as DM was with a party that came to the table expecting a TPK; expecting multiple TPKs for that matter. And we had them, too. (Satisfied sigh...) For me, though, this is the exception, not the rule, and the players were totally on board.
You've got to make certain your players are comfortable with death before you can get comfortable with the idea of really threatening them with it, otherwise, someone's bound to get angry. Even then, avoid the attitude that D&D is a DM-vs.-the-Players kind of thing. Instead, make yourself the encouraging referee in their heroic stories. This approach will help you build encounters that are challenging and heroic, while cooperative instead of confrontational.
Managerial Things to Do
Check the paperwork. Ok. This is the least fun thing in the world for me as DM. Take a step back, check out their character sheets, and make certain that everything is in order and that both you and your players understand the mechanics. If you want to reasonably challenge your players, you have to make sure their characters are "fair".
Avoid the slippery slope of custom favors. One way to define "fair" is to play RAW (rules-as-written). In this style, the DM grants no favors and does not authorize unbalanced, custom equipment, races, or classes. Playing RAW, at least, gives you the hope that your material has been playtested. Now, I like using my imagination and coming up with custom content; however, I know that when doing so, I take the risk that I've given the players something unbalanced.
Constrain Your Literature. The larger your literature, the more capable are your players to create extremely min-maxed characters. My favorite PC was an 8th-level barbarian that did things with a greathammer I had not thought possible at 20th level, but it took sampling from three of the Completes and the PHBII to pull him off. I found that the most effective way to control the size of our literature was to insist that the group respect intellectual property rights and purchase books before material would be allowed in the campaign.
Cheers!
