This may happen because by converting the dates to varchar you are doing a string comparision. Try this by not converting the dates to varchar.
[Edit]
something like this
select leaveemployeeid from leave where convert(datetime,'23/04/2012') between convert(datetime,'2012-04-23 00:00:00.000') and convert(datetime,'2012-05-04 00:00:00.000')
or
select leaveemployeeid from leave where convert(datetime,'23/04/2012') between startdate and enddate
[/Edit]