This first one is, well, crude and rude but kind of elegant in a way. When the client wants the record have it make the request using a seperate connection from any other SQL it may execute in the mean time. Have the request SP write the connection ID to a table when no record is available. Have the client leave the connection open after the SP returns no record. Have the client check the status of the connection periodically (rather than requery). When the server finds that a record is now available, have it query the table for all the waiting connections and KILL them . The client will then detect that the connection was lost, reconnect, and re-request the record. If the connection was lost due to some network problem or an idle timeout or whatever then it will just go into a holding pattern again. I would capture the Login Time in addition to the process ID of the connection and prior to KILLing it verify that the current version of the process ID has the same Login Time as the one in the table just in case the connection was closed without cleaning up the table and then the process ID reused for a completely different connection. If your "check the status of the connection" timer is really short (less than 10 seconds or so) you should wait a random number of milliseconds (0.000 - 10.000 seconds perhaps) to prevent a ton of connection requests hitting the server all at once.

Another option would be to use sp_cmdShell to run something (anything really) from the OS. You will still have to have a table, perhaps to record the list of people to be notified and perhaps the machine name/port needed to contact them (depends on how you choose to contact them). Very flexible. One way or another it could definately work.