The problem with asking for a fee is that Europe operates under the "transaction takes place at the buyer's location" model for such transactions, meaning you have to collect and report VAT on those fees in each country you have a paying user in. (The same goes for state sales tax in most US states).

If a site makes its money from ads, on the other hand, the location of the visitors is irrelevant when it comes to taxation. The payments from the ad network will just be ordinary business income at the place the site is located.

I don't think the charge a fee model has a chance, except for a few large sites, until some sort of intermediate service is developed that isolates the sites from having to deal with taxes in a bazillion jurisdictions. Something like a Spotify for site access, where users can pay the service a subscription fee, and the service pays sites after taking care of the appropriate taxes on the user's subscription fees so that the sites don't have to deal with it.

And how does one track if payment has been made without using a cookie?

From cameron90 above:

Shopping baskets, load balancer cookies and login tokens are fine (provided you only use them for those purposes!).

Third party advertising tracking cookies are absolutely not (without consent).

By the information a payment provider sends back.

Edit: guess somebody never integrated a payment provider :-)