JavaScript Custom Buttons. I have not been using JavaScript Custom Buttons for a while now, not only are they slower to respond in some cases, for reasons I've never really got to the bottom of. But they force us to expose global / web service classes for code that would otherwise be internal to our solutions.
Visualforce / Apex Custom Buttons. As you've considered in your question, using a Visualforce Page is another, much more direct and modern option in my view. It has now been available for sometime as an alternative, giving you a 100% Apex native solution without having to expose anything via Web Services.
By using the action attribute on the apex:page element you can invoke some Apex controller logic when your page is loaded by the button. Then return the PageReference you want to redirect the user to. Create a page as follows and then when creating the Custom Button select the List Button type and Visualforce option to select the desired page (note the use recordSetVar to denote a List View page).
<apex:page standardController="Test__c" extensions="ListViewActionController"
recordSetVar="TestRecords" action="{!doSomething}"/>
The following action controller method performs the neccessary work and redirects back to the list view.
public with sharing class ListViewActionController {
public ListViewActionController(ApexPages.StandardSetController stdController) { }
public PageReference doSomething()
{
// Do something...
insert new Test__c();
// Invoke the list action to return back to the ListView
return new ApexPages.Action('{!list}').invoke();
}
}
Salesforce Security Review. Keep the following in mind, if your building a managed package and planning on taking it through this process. Action methods invoked on page load that perform database modifications, are generally (without further discussion) not accepted. Instead you need to modify your page to provide a button the user has to press.
<apex:page standardController="Test__c" extensions="ListViewActionController" recordSetVar="TestRecords">
<apex:form >
<apex:pageMessage summary="Click 'Do Something' to confirm." severity="Info" strength="2"/>
<apex:commandButton value="Do Something" action="{!doSomething}"/>
<apex:commandButton value="Back" action="{!list}"/>
</apex:form>
</apex:page>

Hope this helps, enjoy!
setTimeout
)?location.reload()
or when I had to work on one checkbox at a time I've been displaying "Processing 3 out of 10 records" as the button name... If you're sure then it might be tricky to work with... Does addingsforce.debug.trace=true;
change anything?