I just stumbled on this this morning, coincidentally after reading the Mail.app sub-folder hint.
In Acrobat Professional, if you use File: Save As, you can include a new folder in the file's name. So if you name the file NewFolder/untitled.pdf, Acrobat will create a new folder called 'NewFolder' with the 'untitled.pdf' PDF file inside.
Mac OS X Hints
http://hints.macworld.com/article.php?story=20050809120957201