PSNR, Bitrate of Full Search and other algorithms

Hi guys,
Sorry if this question make you feel uncomfortable because it is not
related to XVID, but more related to Motion Estimation algorithm in video
compression. I am implementing new search algorithm that is used in motion
estimation. The interesting point is that the new algorithm give the bigger
PSNR and lower bit rate in comparison with Full Search algorithm. I tested
this new algorithm on different video sequences here
http://trace.eas.asu.edu/yuv/ and I still got the same results (bigger PSNR
and lower bit rate than Full Search). What do you think about this? Is it
normal or just a bugs in my algorithm? and do you guys think it is possible
that sometimes new algorithm can give bigger PSNR and lower bit rate than
Full Search algorithm? Has any of you experienced this kind of strange
result before?
Thanks in advance!

-- 
Best wishes,

Tran Xuan Chien
University of Information Technology
Phone: (+84) 1692 468 154