I should have posted code in my question as the commenter has suggested. However, I am posting it as part of this answer - which is clearly a sub-optimal solution but serves my purpose.
This is the code I ended up with (omitting the OAuth and service instantiation)
Public Function AddRows(Values As Object()()) As Boolean
Try
'Create dummy rows value payload
Dim cell2add As New CellData
Dim cellval As New ExtendedValue
cellval.NumberValue = 0
cell2add.UserEnteredValue = cellval
Dim data2add As New RowData
data2add.Values = {cell2add}
Dim rowdataList As New List(Of RowData)
For i = 0 To UBound(Values)
rowdataList.Add(data2add)
Next
'Add a request to append to the sheet's data (expand grid)
Dim appendRequest As New AppendCellsRequest
appendRequest.SheetId = SheetID
appendRequest.Rows = rowdataList.ToArray
appendRequest.Fields = "*"
Dim request As New Request
request.AppendCells = appendRequest
'Execute the request
Dim bRequest As New BatchUpdateSpreadsheetRequest
bRequest.Requests = {request}
Dim bResponse As BatchUpdateSpreadsheetResponse = Service.Spreadsheets.BatchUpdate(bRequest, DataBaseName).Execute()
'Now update the newly added rows with data
Dim index As Integer = GetRowCount() - Values.Length + 2 'GetRowCount() calls the service to get sheet metadata and returns the rows of data (excluding the headers)
Dim vals As New ValueRange
vals.Values = Values
Dim urequest As SpreadsheetsResource.ValuesResource.UpdateRequest =
Service.Spreadsheets.Values.Update(vals, DataBaseName, Name & "!A" & index)
urequest.ValueInputOption = SpreadsheetsResource.ValuesResource.UpdateRequest.ValueInputOptionEnum.USERENTERED
Dim response As UpdateValuesResponse = urequest.Execute
Return response.UpdatedRows = Values.Length
Catch ex As Exception
Trace.WriteLine(Now.ToLongTimeString & ":" & ex.Message)
Return False
End Try
End Function
In short, I am calling AppendCells to expand the size of the 'grid' and then am updating values in the blank rows thus created. If you try to update values for the new row, the server returns a 'Service not available' error. I found the issue when I experimented with updating values (values.batchUpdate) in existing rows and adding new rows in the same request. The error message in that case spoke of 'beyond the grid' updates.