Ok, the fact that too many people are obsessed with game mechanics is a problem, not with the game, but with the people obsessed.
Example:
I program on ocassion, i choose a programming language that i think best fits my requirement for the end result (the program) and i am familiar enough with to achieve that end result. I use the programming language to get an end result (the program), how i get to the end result isn't that important, just that i get there. But i have to use the programming 'rules' for that language to make the program work. If the language doesn't do exactly work like i want it to, i have a few options, i can work around the problem, i can add to the language, i can choose another language, or i can drop the whole idea.
The same goes for RPGs, we chose D&D3E as our rpg rules, so we should stick to those rules. We want an end result (an encounter in this situation), we have the option to write a new game mechanic, use the rules as they are, use a different rules set, or drop the whole idea altogether.
I'm guessing that dropping the idea and going for another rules system aren't an option, so we're stuck with writing a new rules mechanic or using the rules.
Writing a new rules mechanic: Is way to much work in this instance imho.
Using the rules: You have a couple of options (in order of easyness):
1.) Bluff states that you can get situational modifiers depending on how much the recepient wants to believe you (-5 on sense motive). "Hello mister, i lost my puppy *pouting eyes* could you help me look for it?"
2.) Get a situational modifier of +x. The girl knows things about the village that the pcs don't, even if those details are made up. "But mister phisher said, that's the man that bakes bread, that if i was a good girl and hid in the closet i would get a treat. And now everyone's gone! *starts to cry*"
3.) Redistribute some skill points to give the imp some ranks in bluff.
4.) Give the Imp an Int of 12 instead of 10, obviously this isn't your average imp. This would result in 6 extra skill points, that's either Bluff 6 (class skill) or Bluff 3 (not class skill), depending on whether you decide if Bluff is an Imp class skill (going with non class skill would be most save).
5.) Give the imp an extra HD, results in extra skill points.
6.) Give the imp a class level, rogue would be best.
There are a few more options, such as changing the feat selection of the imp, giving it a magical item, or combining any of the above.
The point is to be creative with the rules and not only with the story line. If you still feel that the D&D3E rules limit you to much, maybe writing your adventure for D&D3E wasn't a good idea. You might want to consider writing it for a different, more open game system.
Imho, being a good storyteller isn't enough as a game-writer or DM, you also need to understand the rules set your writing/DMing for and be creative in it's use. If you can't maybe you should consider another line of work. No offense intended, but it's just how i see things, i for one am just not cut out to be a professional programmer because i don't (yet) fully grasp the full extend of the programming languages i work with.