Sorry for the long radio silence. Busy busy busy and this isn't a quicky.
Tip when you're debugging, tidy the code. Indent it nicely, remove blocks of newlines and remove things you don't use like mySerial.
#include <Adafruit_GFX.h>
#include <Adafruit_SSD1306.h>
#include <avr/pgmspace.h>
#include <SoftwareSerial.h>
int menuLength;
int maxItemsPerScreen;
const int fontSize = 8;
static int pinA = 2; // Our first hardware interrupt pin is digital pin 2
static int pinB = 3; // Our second hardware interrupt pin is digital pin 3
static int enSW = 9;
volatile byte aFlag = 0; // let's us know when we're expecting a rising edge on pinA to signal that the encoder has arrived at a detent
volatile byte bFlag = 0; // let's us know when we're expecting a rising edge on pinB to signal that the encoder has arrived at a detent (opposite direction to when aFlag is set)
volatile uint16_t encoderPos = 0; //this variable stores our current value of encoder position. Change to int or uin16_t instead of byte if you want to record a larger range than 0-255
volatile uint16_t oldEncPos = 0; //stores the last encoder position value so we can compare to the current reading and see if it has changed (so we know when to print to the serial monitor)
volatile byte reading = 0; //somewhere to store the direct values we read from our interrupt pins before checking to see if we have moved a whole detent
#define OLED_RESET 4
Adafruit_SSD1306 display(OLED_RESET);
PROGMEM const char Messaging[] = "Messaging";
PROGMEM const char UVScanner[] = "UV Scanner";
PROGMEM const char SecuritySystem[] = "Security";
PROGMEM const char BACK[] = "Main Menu";
int i = 0;
//int itemSelected, subMenuSelected;
//int itemsToDisplay=0;
int curPos, startPos, endPos;
const char* menu_table[] = {Messaging, UVScanner, SecuritySystem, BACK};
void setup() {
display.begin();
pinMode(enSW, INPUT_PULLUP);
pinMode(pinA, INPUT_PULLUP);
pinMode(pinB, INPUT_PULLUP);
attachInterrupt(0, PinA, RISING);
attachInterrupt(1, PinB, RISING);
MySerial.begin(1200);
}
void loop() {
display.setTextSize(fontSize / 8);
display.clearDisplay();
display.setCursor(25, 0);
display.setTextColor(WHITE);
display.println(F("MENU SYSTEM"));
display.setCursor(20, 25);
display.println(F("Press control to enter the menu system"));
display.setTextSize(fontSize / 8);
display.display();
// Build the top level menu if select Switch is pressed
if (digitalRead(enSW) == 0) {
while (digitalRead(enSW) == 0); //wait till switch is released.
menuLength = 4;
maxItemsPerScreen = 4;
Buildmenu(maxItemsPerScreen, menuLength);
}
}
/*******************************Utility Functions *******************************/
void PinA() {
cli(); //stop interrupts happening before we read pin values
reading = PIND & 0xC; // read all eight pin values then strip away all but pinA and pinB's values
if (reading == B00001100 && aFlag) { //check that we have both pins at detent (HIGH) and that we are expecting detent on this pin's rising edge
encoderPos --; //decrement the encoder's position count
bFlag = 0; //reset flags for the next turn
aFlag = 0; //reset flags for the next turn
}
else if (reading == B00000100) bFlag = 1; //signal that we're expecting pinB to signal the transition to detent from free rotation
sei(); //restart interrupts
}
void PinB() {
cli(); //stop interrupts happening before we read pin values
reading = PIND & 0xC; //read all eight pin values then strip away all but pinA and pinB's values
if (reading == B00001100 && bFlag) { //check that we have both pins at detent (HIGH) and that we are expecting detent on this pin's rising edge
encoderPos ++; //increment the encoder's position count
bFlag = 0; //reset flags for the next turn
aFlag = 0; //reset flags for the next turn
}
else if (reading == B00001000) aFlag = 1; //signal that we're expecting pinA to signal the transition to detent from free rotation
sei(); //restart interrupts
}
void Buildmenu( int maxItemsPerScreen, int menuLength) {
do {
startPos = encoderPos % menuLength;
display.clearDisplay();
endPos = maxItemsPerScreen;
if (menuLength < maxItemsPerScreen){
endPos = menuLength - startPos;
}
if ((menuLength - startPos) < maxItemsPerScreen){
endPos = menuLength - startPos;
}
for (int i = 0; i <= endPos - 1; i++) {
if (i == 0){
display.setCursor(0, 0);
display.print(F("Scroll to select"));
display.drawFastHLine(0, 10, 200, WHITE);
display.setCursor(0, 16 + i * fontSize); // sets the selection pointer
display.print(F("->"));
}
display.setCursor(16, 16 + i * fontSize); // sets the height of the submenu text
display.println((__FlashStringHelper*)menu_table[i + startPos]);
display.setCursor(16, 16 + i * fontSize); // sets the height of the submenu text
display.println((__FlashStringHelper*)menu_table[i + startPos]);
display.setCursor(16, 16 + i * fontSize); // sets the height of the submenu text
display.println((__FlashStringHelper*)menu_table[i + startPos]);
display.setCursor(16, 16 + i * fontSize); // sets the height of the submenu text
display.println((__FlashStringHelper*)menu_table[i + startPos]);
}
display.display();
i = 0;
if (oldEncPos != encoderPos) {
oldEncPos = encoderPos;
}
} while (digitalRead(enSW));
while (digitalRead(enSW) == 0); //wait till switch is reseleased
i = 0;
return startPos;
}
Look better already doesn't it? 
Alright, off to the races. First thing I notice is that you have a bunch of printing in the loop(). Is it really needed to print the same over and over again?
Next, the whole thing is till blocking.
if (oldEncPos != encoderPos) {
oldEncPos = encoderPos;
}
Not very usefull to store the old position if you never use it
And you still read encoderPos without disabling interrupts which can give you false readings.
Alright, lets start over. I'll leave the encoder part in. The idea of non-blocking code is to only do thing when you want to. That's why you copied :
if (oldEncPos != encoderPos) {
oldEncPos = encoderPos;
}
From somewhere. Not very usefull to store the old position if you never use it
So just store where you are in the menu and update the screen when it changes.
I made a small start to do it non-blocking. It's not complete, might contain errors and may differ from your idea, but it gives you an idea how to do it. I just reused your encoder code but use Bounce2 library for the button. It's in the attachment because it's a bit long.
menuProgmem.ino (5.51 KB)