Unfortunately, nowadays, most plastic bags are made from biodegradable stuff, which just turns into little fluffy bits of nothing really quickly, so plarn isn't as great as an option as it could be.

However, I think I might try some nice nylon twine or something equally synthetic - that might last a lot longer and it's in a lot more colours.