Based upon an old SP I have I came up with this:

ALTER PROCEDURE [dbo].[sp_Read]

AS

BEGIN

declare @sSQL varchar(5000)

set @sSQL = COALESCE(@sSQL + ' ','')

create table #MyHead (

Pr_Id int,

Pr_Em_Id int,

Pr_Em_Name nvarchar(50),

SortBy int,

Random int IDENTITY(1,1) )

set @sSQL = 'SELECT Pr_Id, Pr_Em_Id,Pr_Em_Name, '

set @sSQL = @sSQL + ' CAST(NULL AS INT) AS SortBy'

set @sSQL = @sSQL + ' FROM tblTemp'

insert into #MyHead

exec(@sSQL)

--===== Add the necessary clustered index for the "quirky" update

CREATE CLUSTERED INDEX IXU_#MyHead ON #MyHead (Pr_Em_Id,Random)

--===== Create a couple of variables to use in the "quirky" update and preset them

DECLARE @PrevSortBy INT,

@PrevPr_Em_Id INT

SELECT @PrevSortBy = 0,

@PrevPr_Em_Id= 0

--===== Do the "quirky" update. Think of it as "ROW_NUMBER() OVER" for SQL Server 2000

UPDATE #MyHead

SET @PrevSortBy = SortBy = CASE WHEN @PrevPr_Em_Id = Pr_Em_Id

THEN @PrevSortBy + 1

ELSE 1

END,

@PrevPr_Em_Id = Pr_Em_Id

FROM #MyHead WITH(INDEX(0))

--===== Produce the "semi random" output.

SELECT tblTemp.Pr_Id, tblTemp.Pr_Em_Id, tblTemp.Pr_Em_Name,Pr_Product

FROM tblTemp INNER JOIN #MyHead ON tblTemp.Pr_Id = #MyHead.Pr_Id

ORDER BY SortBy,case when left(tblTemp.Pr_Em_Name, 1) >= CHAR(65 + 26 * rand()) then 0 else 1 end

--ORDER BY SortBy,Pr_Em_Id --Semi random as requested

drop table #MyHead

END