ユーザーIDにアンダーバー
'@_hogehoge'とか、'@hogehoge_'とかがアウト。
'@hoge_hoge'はセーフ。
参考：「idに「_」、アンダーバーが入ってると検索してもヒットしない。「_」付きidユーザーの発言は検索にヒットしない。見れなくなった。 ←マジかよ…」 - Togetter
ここにまとめられてるのは公式サイトの検索窓だそうですが、Search APIでも同じくです。
ちなみに、"@"を先頭に付けてもダメでした。
どうするか
他の手段をさがす。 →諦める。
Twitter側でどうにかしてくれるのを待つのが吉やと思います。
ユーザーを絞って検索したい以上、ユーザーIDじゃなくてユーザー名を使うなんてありえないし、そもそもそんなパラメータ指定ないし。
20120224追記
なんだか検索されるようになった模様。
めでたしめでたし。
参考：Twitter Search Ignores Underscore '_' when Searching Username - Therefore, results are distorted when username is two words separated by underscore | Twitter Developers