If you observe how the popular caching plugins like WP Super Cache or W3TC utilize a cache folder within wp-content as well as other plugins who utilize uploads or cachable files it would be appropriate to create a folder within that structure. A side issue may arise if the user has a locked down folder structure as you indicated and the plugins folder may be one of those protected areas. In my experience I have seen site owners lock down the file system with flags for cache and uploads in the wp-content folder and this would present a compatiblity challenge for your plugin. Thus in order to be as “WordPressy” as possible I would recommend as a practice to adhere to the general practice of storing created files in appropriate areas that are commonly associated with dynamicly created static assets.
The larger issue of storing static files within your plugin folder is when a plugin update occurs the cached files will be wiped because the folder is replaced during the update process. Again without a custom update mechanism within your plugin (which would prevent it from being submitted to .org repo) you are left with a performance hit on the cached files everytime an update occurs to the code vs the content/usage.
In response to the clarification comments, in theory/practice versioning systems shouldn’t track the uploads unless the sql is also versioned which in this case I wouldn’t be too concerned about it.