That sounds just like parameter sniffing. (http://sqlinthewild.co.za/index.php/2007/11/27/parameter-sniffing/)
Post the code and exec plan?
Does it have to be a function?
Gail Shaw
Microsoft Certified Master: SQL Server, MVP, M.Sc (Comp Sci)
SQL In The Wild: Discussions on DB performance with occasional diversions into recoverability