SELECT INTO creates a new table?
Yes, SELECT..INTO creates a new table

You'd need this to add rows to an existing table

INSERT MessageQueue (MessageQueue, OneId, OtherId) 
SELECT MessageId = 9999, OneId, OtherId 
   from @TempTable