In base R, you could use lapply to go through columns and extract non NA elements and corresponding ID.
do.call(rbind, lapply(df[,-1], function(x)
    data.frame(ID = df$ID[!is.na(x)], VALUE = x[!is.na(x)])))
#       ID VALUE
#COL1.1  1    22
#COL1.2  2     2
#COL1.3  3     1
#COL2.1  1    12
#COL2.2  3     2
#COL3    3     4
If necessary, the order can be changed in one additional step
df2 = do.call(rbind, lapply(df[,-1], function(x)
    data.frame(ID = df$ID[!is.na(x)], VALUE = x[!is.na(x)])))
do.call(rbind, split(df2, df2$ID))
#         ID VALUE
#1.COL1.1  1    22
#1.COL2.1  1    12
#2         2     2
#3.COL1.3  3     1
#3.COL2.2  3     2
#3.COL3    3     4
DATA
df = structure(list(ID = 1:4, COL1 = c(22L, 2L, 1L, NA), COL2 = c(12L, 
NA, 2L, NA), COL3 = c(NA, NA, 4L, NA)), .Names = c("ID", "COL1", 
"COL2", "COL3"), class = "data.frame", row.names = c(NA, -4L))