Please let me know what type of Traces I can run to identify the underlying cause. Both setup are in Dev. Same everything but 100x slower. Each Dev sql-server has it's own separate identical virtual machine. Statistics are almost identical, rowcount, index defrag %. No contention on the server to worry about locks & latches. This is a real brain teaser for me. We're on Sql 2000 sp3a though planning to upgrade to 2005.

declare
    @AN_CustID int,
    @LastName varchar(30),
    @FirstName varchar(30)
select @AN_CustID = 2824, @LastName = 'XXXXX', @FirstName = 'XXXXX'

SET NOCOUNT ON

DECLARE @SdxLastName char(4)
DECLARE @TheFirstName varchar(30)
DECLARE @HitCountLastNameOnly int
DECLARE @HitCountFirstName int
DECLARE @ThresholdLastName int
DECLARE @ThresholdFirstName int

-- Set minimum row hit count for when to use the first name in addition to last name for search
SET @ThresholdLastName = 2 --if we get at least this number of rows back, ignore the first name completely
-- Set maximum row hit count for when to use the exact first name instead of first name soundex in addition to last name soundex for search
SET @ThresholdFirstName = 12 --if we get over this number of rows back, look for exact first name match

SELECT
        @AN_CustID = ISNULL(@AN_CustID, 0),
        @LastName = RTRIM(ISNULL(@LastName, '')),
        @FirstName = RTRIM(ISNULL(@FirstName, ''))

IF @AN_CustID < 1 OR @LastName = '' RETURN --required params

-- Whenever a doctor's first name is unknown, the user will enter "DR"; therefore, do not soundex the first name in this case
IF @FirstName='DR.' OR @FirstName='DR' SET @FirstName=''

-- Get the soundex of the specified physician
SELECT @SdxLastName = dbo.aif_Soundex(@LastName), @TheFirstName = dbo.aif_Soundex(@FirstName)

-- Determine how many rows are returned based solely on similarity of the last name
SELECT
        @HitCountLastNameOnly = COUNT(*) FROM PhysicianMstr p (NOLOCK)
WHERE
        p.AN_CustID = @AN_CustID
        AND p.Active = 1
        AND @SdxLastName = dbo.aif_Soundex(RTRIM(p.LastName))

-- Check if using just the last name soundex returns too few rows
IF @HitCountLastNameOnly < @ThresholdLastName
BEGIN
        -- Determine how many rows are returned based on last name soundex or first name soundex
        SELECT
                @HitCountFirstName = COUNT(*)
        FROM PhysicianMstr p (NOLOCK)
        WHERE
                p.AN_CustID = @AN_CustID
                AND p.Active = 1
                AND (
                        @SdxLastName = dbo.aif_Soundex(RTRIM(p.LastName))
                        OR @TheFirstName = dbo.aif_Soundex(RTRIM(p.FirstName))
                        )
        -- If too many rows, switch to exact match on first name instead of soundex of first name
        IF @HitCountFirstName > @ThresholdFirstName
        BEGIN
                SET @TheFirstName = @FirstName
                SET @HitCountLastNameOnly = -1 --negative value indicates first name exact match, not soundex
        END
END

-- List physicians with similar sounding names
SELECT
        p.AN_PhysicianID,
        pm.AN_CustID,
        RTRIM(p.LastName) AS LastName,
        RTRIM(p.FirstName) AS FirstName,
        RTRIM(p.StateLicNo) AS UPIN,
        RTRIM(mis.Specialty) AS Specialty1,
        pm.Specialty2,
        p.Active,
        RTRIM(pm.Degree) AS Degree,
        pm.Extra,
        p.CreatedBy,
        p.CreatedOn,
        p.ModifiedBy,
        p.ModifiedOn,
        p.PLEPhysicianMIID
FROM
        PLEPhysicianMstrMI p (NOLOCK)
        INNER JOIN PhysicianMstr pm (NOLOCK) ON
                p.AN_PhysicianID = pm.AN_PhysicianID
        LEFT JOIN PLEPhysicianSpecialtyMstrMI mis (NOLOCK) ON
                p.PLEPhysicianSpecialtyMIID = mis.PLEPhysicianSpecialtyMIID
WHERE
        pm.AN_CustID = @AN_CustID
        AND p.Active = 1
        AND (
                @SdxLastName = dbo.aif_Soundex(RTRIM(p.LastName))
                OR @TheFirstName =
                        CASE
                                -- Include first name only when we don't have the minimum number of rows
                                WHEN @HitCountLastNameOnly < 0 THEN p.FirstName --exact first name match
                                WHEN @HitCountLastNameOnly < @ThresholdLastName THEN dbo.aif_Soundex(RTRIM(p.FirstName))
                                ELSE '****' --force false for first name test
                        END
                )
ORDER BY p.LastName, p.FirstName