For best prices, buy in bulk from Supermediastore and have them shipped to you.
I use Verbatim and Memorex
You might try without labels if you still have problems with the new discs, but if they work, good for you.
Yes and many more. Have a look at Wikipedia for details.