Some musing here, but take a look at the last paragraph if you don't want to wade through the rest.
Let's go back to your original idea of a Web service.
To make floating licenses work, your clients (the end users) need access to the license file (KeyStore) on the server. Is there some way you can contrive to have a Web service provide this 'access?' I believe the client has to think it has run an executable located on your key server.
This might prove tricky, since you'd in essence be passing an executable through a Web service. However, perhaps it could work somehow. You are only passing outwards, which may mitigate firewall concerns. And you might only need to pass as far as the Web service host, since access to the program could likely be served from there.
A tricky part might be handling the current status of your licenses (available and reserved). This context likely needs to stay with KeyStore. Somehow you've got to capture it and provide it to the spot from which the Web service actually points your clients.
AFAIK, floating licenses can be divided into pools, which you've tried. The big problem here is that you can't divide too many times (a single division is often too many) before each of the pools seems to be the wrong size. Unless you have a really big user community you'll quickly be faced with an inventory of unused licenses in one pool and disconnected users queued up at the other. Adjusting the pools would take time, irritate everyone, and merely move the problem around so everyone gets to experience all the problems.
Perhaps you can create a Web service that directly serves access to KeyStore, and make it available to everyone who can authenticate at the Web service level, inside and out. Would this work for your security infrastructure? You might have to let internal users connect indirectly, by going right out to the internet and back in to your Web service (rather than via your intranet).
At the very least, the ability to connect via a Web service is worth raising a feature request with Sparx. We (the 'regulars' in this forum) have a set practice for doing these, which helps keep us all in the loop. You can do a search for recent (past few months) posts using the keywords "Request-a-Feature" or "Feature Request" (without quotes) and perhaps "Best Practice" as well. This will walk you through. I'd support this, and I'm sure others would too. The nice thing is that this would not require extensive change to the core EA product, so could be done at any time - it would be less likely to be postponed to the "next major version."
David