Why don't u use MSSQL with a good ol stored procedure?You have it installed anyway.It may be done i sqldatasource but i would urge you not to use this control.Also don't use "*" for selecting data, use the columns names.
The "as new" question, is blurry.What do you define as new?If you define a column named as messagestatus in sql then you can "select blah, form tableblah WHERE [SentTo] = @SentTo and messagestatus=1 order by etc etc.
Assuming that when messagestatus gets the number 1 then it's a new message,or unread message or something.