Judging from what I'm reading it seems e-cheques in general just aren't trusted much by sellers. I don't know if it applies but apparently some people can even opt to automatically reject e-cheque payments, like on Ebay, for instance. Same applies to some banks which will reject as well, while others might accept. It might explain why your e-cheques sometimes go through and sometimes don't, if you're sending money to different places. I'm no expert so I can't be too sure, though. :x Hope you're able to get things to work out.
As a side note, have you linked your actual bank account to Paypal? I know you've linked your credit card but your account doesn't get verified till you link your bank account. I thought I was verified too at first but you actually have to give them your checking account + routing number, they'll send two small deposits of money and you input those amounts back on their site to verify that its your account. Then you'll be able to send money directly from it, I think. You should be able to even if it's a Canadian bank account, I googled "How do I confirm my Canadian bank account? - PayPal" and it's answered right on their site. They have pictures illustrating which numbers they need on their site while you're applying to link your bank account, too.
When you register your Canadian bank account, PayPal makes two small deposits to your bank account, each for an amount between .01 CAD and .99 CAD.
These deposits should post to your bank account within 2-3 business days. To find the amounts of the deposits, you can look at your online account statement or contact your bank's customer service department.
When you know the amounts of the deposits, log in to your PayPal account and click the Confirm Bank Account link on your Account Overview page to enter the amounts.