The option to "Mark as Up-to-Date" is, I think, only available for photos in the "Modified Photos to Re-Publish" queue. It does not seem to be available for any in the "New Photos to Publish" queue, which I guess all your photos are if you deleted and recreated the service.
That really stinks considering the workaround for the flickr bug in LR4 was to delete the service and recreate it...now I can't use it unless I upload over 160 photos that are already on flickr. Grrrrr!
I would appeal to the plugin author. It's entirely possible to add a "Mark As Published" feature to apply to "Not Considered Published Yet" photos. Lightroom alone can't do it, since the publishing service itself needs info unique to the publishing service / photos...
Don't get me wrong: I'm not saying there isn't room for improvement by way of Adobe / Lightroom - just that you are far more likely to get the feature you want sooner by going to the plugin author(s).
Example from Photooey Publisher:
Now that I think about it, have you tried Jeffrey Friedl's Flickr publishing plugin? - It may already have this feature(?)
I sympathise with your position.
In case you are not aware of it, there is an alternate way of publishing to Flickr from LR using the plugin created by Jeffrey Friedl.
It is highly regarded, highly functional and I believe it will synchronise to an existing set of photos already uploaded - I'm not sure if the built in LR one will, if you create a new service.
If interested see ...http://regex.info/blog/lightroom-goodies/flickr/publish
It's not an option that I personally use because my needs are simpler and I will always try to make do with an out of the box solution - a personal choice.
FYI - I have recently migrated to LR4.1 RC2 from LR4.0 and the Flickr publish seems to work fine except if you have a Line feed or Carriage return in your photo caption - in which case LR cannot contact Flickr and suggests your internet connection may be broken - in summary, it is still not without issues