If System Restore isnt available then one option is If you can find the
executable that runs the file (The .exe file you double click to run the
program) then right click and choose 'copy' then goto the startup folder and
paste it into there.
C:\Documents and Settings\Your Username\Start Menu\Programs\Startup
when you open the Startup folder right click an empty space and choose
'paste', you will then get another alert from Microsoft Antispyware showing a
new Start up Program, choose Allow and it will then start with Windows.
If you let us know the program and what Version of Windows you are using
then its quite easy to add the entry back into the registry in the correct
location as the start up menu will load the program but its not going to
replace the entry you removed by mistake.
Andy