I guess you somehow ignored the second part of my message. If in your VB Code you make use of Command object, this would be much better. Following is the segment that should return the new value to you.
Dim mcmd as ADODB.Command
mcmd.CommandType=adCmdStoredProc
mcmd.CommandText="AddRecord"
dim mParam as ADODB.Parameter
Set mParam = mCmd.CreateParameter("MyNewKey",adinteger,adParamOutput)
mCmd.Parameters.Append mParam
mcmd.Execute
msgbox mcmd(0)