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)