OK, I got it working. Basically, the solution has 2 parts:
- make the HTTP request manually (with any required credentials or headers)
 
- wrap the response stream in a custom 
IRandomAccessStream that implements Seek by making another request to the server, using the Range header to specify which part of the stream I need. 
Here's the RandomAccessStream implementation:
delegate Task<Stream> AsyncRangeDownloader(ulong start, ulong? end);
class StreamingRandomAccessStream : IRandomAccessStream
{
    private readonly AsyncRangeDownloader _downloader;
    private readonly ulong _size;
    public StreamingRandomAccessStream(Stream startStream, AsyncRangeDownloader downloader, ulong size)
    {
        if (startStream != null)
            _stream = startStream.AsInputStream();
        _downloader = downloader;
        _size = size;
    }
    private IInputStream _stream;
    private ulong _requestedPosition;
    public void Dispose()
    {
        if (_stream != null)
            _stream.Dispose();
    }
    public IAsyncOperationWithProgress<IBuffer, uint> ReadAsync(IBuffer buffer, uint count, InputStreamOptions options)
    {
        return AsyncInfo.Run<IBuffer, uint>(async (cancellationToken, progress) =>
        {
            progress.Report(0);
            if (_stream == null)
            {
                var netStream = await _downloader(_requestedPosition, null);
                _stream = netStream.AsInputStream();
            }
            var result = await _stream.ReadAsync(buffer, count, options).AsTask(cancellationToken, progress);
            return result;
        });
    }
    public void Seek(ulong position)
    {
        if (_stream != null)
            _stream.Dispose();
        _requestedPosition = position;
        _stream = null;
    }
    public bool CanRead { get { return true; } }
    public bool CanWrite { get { return false; } }
    public ulong Size { get { return _size; } set { throw new NotSupportedException(); } }
    public IAsyncOperationWithProgress<uint, uint> WriteAsync(IBuffer buffer) { throw new NotSupportedException(); }
    public IAsyncOperation<bool> FlushAsync() { throw new NotSupportedException(); }
    public IInputStream GetInputStreamAt(ulong position) { throw new NotSupportedException(); }
    public IOutputStream GetOutputStreamAt(ulong position) { throw new NotSupportedException(); }
    public IRandomAccessStream CloneStream() { throw new NotSupportedException(); }
    public ulong Position { get { throw new NotSupportedException(); } }
}
It can be used like this:
private HttpClient _client;
private void InitClient()
{
    _client = new HttpClient();
    // Configure the client as needed with CookieContainer, Credentials, etc
    // ...
}
private async Task StartVideoStreamingAsync(Uri uri)
{
    var request = new HttpRequestMessage(HttpMethod.Get, uri);
    // Add required headers
    // ...
    var response = await _client.SendAsync(request);
    ulong length = (ulong)response.Content.Headers.ContentLength;
    string mimeType = response.Content.Headers.ContentType.MediaType;
    Stream responseStream = await response.Content.ReadAsStreamAsync();
    // Delegate that will fetch a stream for the specified range
    AsyncRangeDownloader downloader = async (start, end) =>
        {
            var request2 = new HttpRequestMessage();
            request2.Headers.Range = new RangeHeaderValue((long?)start, (long?)end);
            // Add other required headers
            // ...
            var response2 = await _client.SendAsync(request2);
            return await response2.Content.ReadAsStreamAsync();
        };
    var videoStream = new StreamingRandomAccessStream(responseStream, downloader, length);
    _mediaElement.SetSource(videoStream, mimeType);
}
The user can seek to an arbitrary position in the video, and the stream will issue another request to get the stream at the specified position.
It's still more complex than I think it should be, but it works...
Note that the server must support the Range header in requests, and must issue the Content-Length header in the initial response.