Your concern regarding updating every relevant user row every 20 seconds or so is totally valid. One solution, then, is to store this data in a single row rather than using the metadata APIs or custom SQL to associate the data with each individual user. The Options API as well as the Transients API are both well suited to this task.
Using the Transients API provides a few additional benefits – in using an expiration time you could easily throttle the updates (i.e. even though you parse the XML 3 times a minute, you could update online status once a minute) and – perhaps more importantly – if you use a caching plugin on your site, the plugin may support keeping transient data in memory in between requests, further reducing database interactions.
As the 4 digit profile ID serves as identifying information associated with a single WordPress user and is unlikely to change frequently, it is best if the profile ID is still stored as user meta-data. Given that online/offline status is a binary state (users must be one or the other), you can get by storing just one of your arrays – i.e. if a user is in the array, they are online. If not, they are offline.
Which data you store in the transient is somewhat dependent on your application. Storing WordPress user IDs seems somewhat unreasonable, as it means you’d be running a user query to determine which WordPress IDs compose your the “online list” every time you update the list. Rather, simply storing the array of user profile IDs with online status may be more performant – when you need to display a user’s online status, use the meta-data API to acquire their profile ID, and then simply check whether or not that profile ID is in your “profiles online” transient. If you need a list of WordPress users with online status, run a user query with a meta-query to find users with profile IDs contained in the transient.
As a final note, don’t update the transient data every time you parse the XML. Instead, create your array of online profiles from the XML data, then use two calls to array_diff() compare the elements in the XML-produced array against the one in transient data. If either resulting array has a length greater than 0, the “online list” has changed, and you should update the transient. This will save several more potential database interactions.