Weddingbee boards

Pearl River Mart on the SoHo/Chinatown border is alwways a good bet. I believe that they also sell through their website.

I agree that Pearl River should have what you need.  There are also two $1 dollar stores on Mulberry Street (diagonally across each other) in between Canal and Bayard Street.  Their inventory fluctuates and the store on east side is a little bigger... they are literally across the street from each other so you can go check out both stores.  The staff is not fluent in English, bringing a printout of what you are looking for may help.  

Also, Kam Man (which is around the corner on Canal Street between Mulberry and Mott) might have the lanterns in the basement. 

Lastly, have you tried orientaltrading.com?