The suggestion of doing it in 1&1 is that by going through the process of creating the spam filter again, I suspect 1&1 will recreate the spam folder in Outlook for you. I know the problem is in Outlook, I was just looking for a way of solving it for you.
I assume you have checked all the other folders you have in outlook, in case it has appeared as a sub-folder there somewhere? (I am not sure the search facility will find it as that is designed to hunt for emails by title or content, not folders.)
For future reference, in most Windows applications if you realise you have done something wrong, if you hit "Ctrl Z" it will undo the last action. You can do this repeatedly and undo as many previous actions as the system stores - very useful when you have cocked things up in a big way. Sadly the history of things to undo is lost when you shut down and restart the application, so when you did this you lost the option to undo your move.