Writing a class akin to the DesktopOAuthAuthorization in the LinqToTwitter library is the way to go. The authorization module is pluggable so you can just add the one you wrote even without recompiling the library.
The WindowsCredentialStore does not sound like the appropriate place to store credentials when you're on Azure, I agree. And the DesktopOAuthAuthorization as-is certainly is not appropriate for an Azure worker role as it assumes the currently logged
in user is meaningful and it is not in that context. The WebOAuthAuthorization seems like it would work. I assume you are using that class already in your WebRole to walk the user through authorization. Then the worker role can use that same
class to send authorized messages to Twitter.
As you say though, a database seems most appropriate and you'll very likely want to design your database to suit the needs of your app. Since the db schema is app-specific, you need to write your own implementation of IConsumerTokenManager and pass
it into the WebOAuthAuthorization constructor so it knows how your database works rather than storing tokens in memory which will inevitably get cleared periodically, requiring your users to re-authorize the app, which isn't cool.
Does this help steer you in the right direction?