How can I remove a non-existent/lost device from firefox sync?

As RajaRaviVarma mentioned in a comment, it is now possible to remove devices without the previous workarounds.

Firefox Accounts ("New Sync") includes Devices View (since PR #3724) which can be used to remove a devices as follows:

1. Visit https://accounts.firefox.com (also reachable from the Manage Account link in Sync Settings).
2. Click the Show button adjacent to "Devices & apps".
3. Click Disconnect... adjacent to the device to remove.
4. Provide a reason (or not) and click the Disconnect button in the confirmation window.

Not-really-solutions:

• Disable tab sync in Options → Sync → Manage Account → View Quota, then re-enable it under Sync My...; this will remove all tabs from the server.

• Open all list items. It seems that if you open a remote tab locally, it is removed from the remote device.

• Set up a temporary Firefox profile and set up Sync with the same device name that you want to remove.

There is a way to achieve this using the Reset Sync command in Firefox' sync preferences. From Mozilla's FAQ:

1. Open the Sync options windowpreferences panel.
2. Click Manage Account and then select Reset Sync. A window displaying the Sync options will open.
3. Select the action you want to take:
   • Recommended: Merge this computer's data with my Sync data
   • Replace all data on this computer with my Sync data
   • Replace all other devices with this computer's data
4. Click Continue. A confirmation sheet appears.

The thing we need to do here is to use Replace all other devices with this computer's data. This may be problematic if you have other devices with unsynced changes, so the sync server should be in the desired state before the replace (maybe using merging?), or you should try to save the data on the other devices by other means.